kotlin-coding-challenges

kotlin-coding-challenges copied to clipboard

The solution in binarytree will never validate a right node as long as the left node is present, causing invalid trees with errors further to the right to count as valid.

These tests invalidates the given solution:

    @Test
    fun `Validate invalid BST 1`() {
        // -- -------Tree------------
        //
        //           10
        //          /  \
        //         5    15
        //        /       \
        //       0         20
        //     /  \
        //   -1   999
        // --------------------------

        val node = Node(10)
        node.insert(5)
        node.insert(15)
        node.insert(0)
        node.insert(-1)
        node.insert(20)
        node.left?.left?.right = Node(999)

        isValidSearchBinaryTree(node) shouldEqual false
    }

    @Test
    fun `Validate invalid BST 2`() {
        // -- -------Tree------------
        //
        //           10
        //          /  \
        //         5    15
        //        /       \
        //       0         20
        //                /  \
        //             999    21
        // --------------------------

        val node = Node(10)
        node.insert(5)
        node.insert(15)
        node.insert(0)
        node.insert(20)
        node.insert(21)
        node.right?.right?.left = Node(999)

        isValidSearchBinaryTree(node) shouldEqual false
    }

Suggesting new solution. This one should work for all types implementing Comparable, and validate all nodes.

private fun <E : Comparable<E>> Node<E>.isValidSearchBinaryTree(min: E? = null, max: E? = null): Boolean {
    if (min != null && data < min) {
        return false
    }
    if (max != null && data > max) {
        return false
    }
    
    return left?.isValidSearchBinaryTree(min, data) ?: true &&
            right?.isValidSearchBinaryTree(data, max) ?: true
}

thx for the info Can you open PR please?

thx for the contribution. The chellange has been updated.