BST checker

Given a binary tree, check if its a BST.

Solution

• BST criteria is left child value must be less than root value which must be less than right child vlaue
• Do this recursively for each node in the BST

Code

    def check_bst(node, low=MIN, high=MAX)
        return true if node.nil?

        return false if node.value < low || node.value > high

        check_bst(node.left, MIN, root.value) &&
        check_bst(node.roght, root.value, MAX)
    end

Time complexity

O(n) since we are visiting all the nodes in the tree