Kotlin recursive function: Binary tree as a binary search tree

Kotlin Function: Exercise-12 with Solution

Write a Kotlin recursive function to check if a binary tree is a binary search tree.

Sample Solution:

Kotlin Code:

data class TreeNode(val value: Int, val left: TreeNode?, val right: TreeNode?)

fun isBinarySearchTree(root: TreeNode?): Boolean {
    return isBSTUtil(root, Int.MIN_VALUE, Int.MAX_VALUE)
}

fun isBSTUtil(root: TreeNode?, minValue: Int, maxValue: Int): Boolean {
    if (root == null) {
        return true
    }

    if (root.value < minValue || root.value > maxValue) {
        return false
    }

    return isBSTUtil(root.left, minValue, root.value - 1) &&
            isBSTUtil(root.right, root.value + 1, maxValue)
}

fun main() {
    val BST1 = TreeNode(
        4,
        TreeNode(
            2,
            TreeNode(1, null, null),
            TreeNode(3, null, null)
        ),
        TreeNode(
            6,
            TreeNode(5, null, null),
            TreeNode(7, null, null)
        )
    )

    val BST2 = TreeNode(
        4,
        TreeNode(
            6,
            TreeNode(5, null, null),
            TreeNode(7, null, null)
        ),
        TreeNode(
            2,
            TreeNode(1, null, null),
            TreeNode(3, null, null)
        )
    )

    val isBST = isBinarySearchTree(BST1)
    println("Is BST1 a binary search tree? $isBST")

    val isNotBST = isBinarySearchTree(BST2)
    println("Is BST2 a binary search tree? $isNotBST")
}

Sample Output:

Is BST1 a binary search tree? true
Is BST2 a binary search tree? False

Explanation:

In the above exercise -

The "TreeNode" class has three properties: value, left, and right. The value property holds the value of the node, while left and right represent the left and right child nodes, respectively. These child nodes can be either TreeNode objects or null.

The "isBinarySearchTree()" function takes a root node of a binary tree as a parameter and returns a Boolean value indicating whether the binary tree is a binary search tree (BST). It internally calls the isBSTUtil function to perform the actual BST checking.

The "isBSTUtil" recursive function takes the root node of a subtree, along with the minValue and maxValue constraints. It checks if the subtree is a valid BST by verifying that the value of the current node is within the allowed range defined by minValue and maxValue. If the value is outside the range, it returns false. Otherwise, it recursively calls itself for the left and right child subtrees, adjusting the constraints accordingly.

The "main()" function creates two binary trees, BST1 and BST2, using the TreeNode data class. BST1 represents a valid BST, while BST2 represents an invalid BST.

Kotlin Editor:

Previous: Find maximum depth of binary tree.
Next: Sum of even numbers in a range.