Validate a BST

Problem

With a binary tree as input, determine if the tree is a BST or not

Input

• node: Has 3 properties
  • .val: Integer value of the node
  • .left: A pointer to another node object, or None if null
  • .right: A pointer to another node object, or None if null
• Each value in the tree is a distinct integer

Approach

This problem is slightly tricky because it is not sufficient to simply check whether or not the left child's value is less than the parent node's value and the right child's value is greater than the parent node's value.

Specifically speaking, when traversing down the binary tree and the direction is changed (i.e. from right to left, or left to right), a new boundary is set for all child nodes.

For example, in the binary tree below, 45 is the leaf. 45 is indeed greater than its parent 15, and the subtree only consisting of 15 and 45 is considered a BST, but in the diagram, 45 is greater than 10, while 10 is less than 30. The BST property does not hold because \(45 \nleq 30\).

The approach then is to do the following: When we traverse down a tree, we specify the maximum when we go from right to left, and the minimum when we from left to right. Then we use this (minimum, maximum) range to determine if our left/right child value satisfies the BST property.

Solution

def is_valid_BST(self, root):  
    """
    :type root: TreeNode
    :rtype: bool
    """

    def _is_valid(node, lo, hi):
        if not node:
            return True

        valid = True

        if node.left:
            valid = _is_valid(node.left, lo, node.val) if node.left.val < node.val and node.left.val > lo else False

        if not valid:
            return False

        if node.right:
            valid = _is_valid(node.right, node.val, hi) if node.right.val > node.val and node.right.val < hi else False

        return valid

    return _is_valid(root, -float('Inf'), float('Inf'))