Validate a BST

Question

Given the root of a binary tree, determine whether it is a valid binary search tree (BST). A binary tree is a valid BST when, for every node, all values in its entire left subtree are strictly less than the node's value and all values in its entire right subtree are strictly greater. The rule applies to the whole subtree, not just the immediate children: a value buried deep on the left must still be smaller than every ancestor it sits under on that side.

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def is_valid_bst(root: 'TreeNode') -> bool:
    pass
Input


 	root, the root TreeNode of a binary tree, or None for an empty tree. Node values are integers.

Output


 	A bool: True if the tree satisfies the BST invariant everywhere, otherwise False. An empty tree is a valid BST.

Examples


 	The tree [2,1,3] (root 2, left child 1, right child 3) returns True.
 	The tree [5,1,4,None,None,3,6] (root 5; left child 1; right child 4 whose own children are 3 and 6) returns False. Node 4 is bigger than its left child 3 and smaller than its right child 6, so a child-only check would wrongly accept it, but 3 lives in the right subtree of the root 5 and is smaller than 5, which breaks the invariant.

Accepted Answer

Pass an open interval (low, high) down the recursion: a node is legal only if low < node.val < high. Going left replaces high with the node's value (everything left must be smaller than this node and every ancestor that forced a left turn); going right replaces low. The root starts unbounded. This visits each node once, so it is O(n) time and O(h) space for the recursion stack, where h is the tree height.

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def is_valid_bst(root: 'TreeNode') -> bool:
    def check(node, low, high):
        if node is None:        # an empty subtree is always valid
            return True
        # The node must lie strictly inside the allowed open interval.
        if not (low < node.val < high):
            return False
        # Left subtree: upper bound tightens to node.val.
        # Right subtree: lower bound tightens to node.val.
        return (check(node.left, low, node.val) and
                check(node.right, node.val, high))

    return check(root, float('-inf'), float('inf'))

# Build the example trees by hand and run them.
t1 = TreeNode(2, TreeNode(1), TreeNode(3))
print(is_valid_bst(t1))   # True

t2 = TreeNode(5,
              TreeNode(1),
              TreeNode(4, TreeNode(3), TreeNode(6)))
print(is_valid_bst(t2))   # False

 	The whole point is the inherited bound: when the validator reaches node 3 in the second tree it carries high = 5 from the root's right turn, so 3 < 5 fails the low < node.val < high test even though 3 looks fine next to its own parent 4. A child-only check would miss this.

Title	Category	Subcategory	Difficulty	Status
Balanced Brackets	Programming	Other	Easy	Unlock
Circular Queue Implementation	Programming	Other	Hard	Unlock
Evaluate RPN	Programming	Other	Medium	Unlock
Last Node of Singly Linked List	Programming	Other	Medium	Unlock
Linked List Cycle	Programming	Other	Medium	Unlock
Priority Queue Using Heaps	Programming	Other	Hard	Example
Reverse a Linked List	Programming	Other	Easy	Unlock
Streaming Median	Programming	Other	Hard	Unlock
Weather API Data Analyzer	Programming	Other	Hard	Unlock

The Interview Guide for Quants and Traders

Validate a BST

What do you think of this page?