Check If Tree is Binary Search Tree in Kotlin

by

To check if a binary tree is a binary search tree or not, we can perform an inorder traversal of the tree and check if the resulting sequence is in non-decreasing order.

Here’s a Kotlin code implementation of this approach:

Kotlin
class TreeNode(var `val`: Int) {
    var left: TreeNode? = null
    var right: TreeNode? = null
}
fun isValidBST(root: TreeNode?): Boolean {
    return isValidBSTHelper(root, null, null)
}
fun isValidBSTHelper(node: TreeNode?, min: Int?, max: Int?): Boolean {
    if (node == null) {
        return true
    }
    if ((min != null && node.`val` <= min) || (max != null && node.`val` >= max)) {
        return false
    }
    return isValidBSTHelper(node.left, min, node.`val`) && isValidBSTHelper(node.right, node.`val`, max)
}
fun main() {
    // Create a binary tree
    val root = TreeNode(5)
    root.left = TreeNode(3)
    root.right = TreeNode(7)
    root.left?.left = TreeNode(2)
    root.left?.right = TreeNode(4)
    root.right?.left = TreeNode(6)
    root.right?.right = TreeNode(8)

    // Check if the binary tree is a valid binary search tree
    val isValidBST = isValidBST(root)
    if (isValidBST) {
        println("The tree is a valid binary search tree")
    } else {
        println("The tree is not a valid binary search tree")
    }
}

The isValidBST function takes the root node of a binary tree and returns a boolean indicating whether or not the tree is a binary search tree.

The isValidBSTHelper function is a recursive helper function that performs an inorder traversal of the binary tree and checks if the resulting sequence is in non-decreasing order. The function takes two parameters: the current node being visited (root) and the value of the previous node in the inorder traversal (prev).

The function first checks the left subtree by calling itself recursively with the left child of the current node. If the left subtree is not a valid binary search tree, the function immediately returns false.

The function then checks the current node by comparing its value with the value of the previous node in the inorder traversal (prev). If the current node’s value is less than or equal to the previous node’s value, the function returns false.

Finally, the function updates the value of prev to the current node’s value and checks the right subtree by calling itself recursively with the right child of the current node.

Note that this algorithm has a time complexity of O(n), where n is the number of nodes in the binary tree, since we visit each node in the tree exactly once.

                5
             /   \
           3      7
        /   \   /   \
      2     4 6    8

n this example, a binary tree is created by initializing a root node and assigning left and right nodes to it. Then the isBinarySearchTree function is called on the root node to check if it’s a binary search tree or not. The function returns a boolean value indicating whether the tree is a binary search tree or not. Finally, the result is printed to the console.

Output : The tree is a valid binary search tree

Leave a Comment