98. Validate Binary Search Tree

Description

See: https://leetcode.com/problems/validate-binary-search-tree/

Note that in this version of a binary search trees, that duplicates are not allowed. The problem defines a binary search tree as:

• The left subtree of a node contains only nodes with keys less than the node's key.

• The right subtree of a node contains only nodes with keys greater than the node's key.

• Both the left and right subtrees must also be binary search trees.

Solution

This problem and its solution is also in Cracking the Coding Interview book.

Suppose we have the following tree:

Atribution: Pat Hawks, CC BY-SA 4.0 https://creativecommons.org/licenses/by-sa/4.0, via Wikimedia Commons

The idea to solve this problem is to think of a node as being between two values.

For the root node, 12, since it does not have a parent node, its value can be anything between negative infinity and infinity.

For the root's left child, its value must be between negative infinity and 12. In this case it is 6, so it is valid:

$$left child = -\infty < 6 < 12$$

For the root's right child, its value must be between 12 and infinity. In this case it is 16, so it is valid:

$$right child = 12 < 16 < \infty$$

Moving down the tree, we use the same formula for each node. So for node 6's left child its value must be between negative infinity and 6. For node 6's right child its value must be between 6 and 12.

And so on.

class Solution:
    def isValidBST(self, root: Optional[TreeNode]) -> bool:
        def is_valid(node, left_val, right_val) -> bool:
            if node is None:
                return True
            if not(left_val < node.val < right_val):
                return False

            return is_valid(node.left, left_val, node.val) and is_valid(node.right, node.val, right_val)

        return is_valid(root, float("-INF"), float("INF"))