Validate Binary Search Tree

▶

Steps

setup

Initialize previous value to negative infinity

We start by setting prev to negative infinity to ensure the first node's value will be greater.

💡 This initialization is crucial because it sets a baseline for comparison during traversal.

Line:

prev = [float('-inf')]

💡 The algorithm uses prev to track the last visited node's value in inorder sequence.

traverse

Start inorder traversal at root node (2)

Begin recursion by calling inorder on the root node with value 2.

💡 Starting at the root is the natural entry point for the traversal.

Line:

return inorder(root)

💡 The traversal will explore left subtree first, then node 2, then right subtree.

traverse

Traverse left subtree of node 2

Recursively call inorder on the left child of node 2, which is node 1.

💡 Inorder traversal requires visiting the left subtree before the current node.

Line:

if not inorder(node.left):
    return False

💡 The algorithm moves down to the left child to continue inorder traversal.

compare

Check left child node 1 against prev

Since node 1 has no left child, we check if its value (1) is greater than prev (-inf).

💡 This comparison ensures BST property: current node must be greater than previous inorder node.

Line:

if node.val <= prev[0]:
    return False
prev[0] = node.val

💡 Node 1 is valid because 1 > -inf, so prev is updated to 1.

traverse

Traverse right subtree of node 1 (null)

Call inorder on the right child of node 1, which is null, so return True immediately.

💡 Null nodes are base cases that return True, allowing recursion to continue.

Line:

if not node:
    return True

💡 Leaf node traversal ends here, confirming no violation in this path.

returning

Return from node 1 to node 2

Finished processing node 1, return True to node 2 to continue traversal.

💡 Returning True means no BST violation found in left subtree.

Line:

return inorder(node.right)

💡 Traversal now proceeds to process node 2 itself.

compare

Check node 2 value against prev

Compare node 2's value (2) with prev (1) to ensure BST property holds.

💡 Current node must be strictly greater than prev to maintain BST order.

Line:

if node.val <= prev[0]:
    return False
prev[0] = node.val

💡 Node 2 is valid, update prev to 2.

traverse

Traverse right subtree of node 2

Recursively call inorder on the right child of node 2, which is node 3.

💡 After processing current node, inorder traversal continues to right subtree.

Line:

return inorder(node.right)

💡 Traversal moves to node 3 to validate right subtree.

traverse

Traverse left subtree of node 3 (null)

Call inorder on left child of node 3, which is null, so return True immediately.

💡 Null children are base cases that return True.

Line:

if not node:
    return True

💡 No violation in left subtree of node 3.

compare

Check node 3 value against prev

Compare node 3's value (3) with prev (2) to ensure BST property holds.

💡 Current node must be strictly greater than prev to maintain BST order.

Line:

if node.val <= prev[0]:
    return False
prev[0] = node.val

💡 Node 3 is valid, update prev to 3.

traverse

Traverse right subtree of node 3 (null)

Call inorder on right child of node 3, which is null, so return True immediately.

💡 Null children are base cases that return True.

Line:

if not node:
    return True

💡 No violation in right subtree of node 3.

returning

Return from node 3 to node 2

Finished processing node 3, return True to node 2 to complete traversal.

💡 Returning True means no BST violation found in right subtree.

Line:

return inorder(node.right)

💡 Traversal now completes at root node.

returning

Return final result true

The entire inorder traversal completed without violations, so return True as the BST validation result.

💡 Returning True means the tree satisfies BST properties everywhere.

Line:

return inorder(root)

💡 The algorithm confirms the input tree is a valid BST.

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):
    prev = [float('-inf')]  # STEP 1
    def inorder(node):
        if not node:  # STEP 5, 9, 11
            return True
        if not inorder(node.left):  # STEP 3
            return False
        if node.val <= prev[0]:  # STEP 4, 7, 10
            return False
        prev[0] = node.val  # STEP 4, 7, 10
        return inorder(node.right)  # STEP 5, 8, 11
    return inorder(root)  # STEP 2, 13

if __name__ == '__main__':
    root = TreeNode(2, TreeNode(1), TreeNode(3))
    print(is_valid_bst(root))  # True

📊

Validate Binary Search Tree - Watch the Algorithm Execute, Step by Step

Watching the algorithm step through each node in order reveals how the BST property is checked incrementally, making it easier to understand than just reading code.

213

Current node: 1

213

DFS Stack

1 (entered)

Current node: 2

213

DFS Stack

2 (entered)1 (left_done)

Current node: 2

213

DFS Stack

2 (entered)prev=11 (left_done)prev=1

Current node: 2

213

DFS Stack

2 (right_done)prev=11 (left_done)prev=1

Return: true

Current node: 1

213

DFS Stack

1 (left_done)prev=1

Current node: 1

213

DFS Stack

1 (left_done)prev=2

Current node: 3

213

DFS Stack

3 (entered)prev=21 (right_done)prev=2

Current node: 3

213

DFS Stack

3 (left_done)prev=21 (right_done)prev=2

Return: true

Current node: 3

213

DFS Stack

3 (entered)prev=31 (right_done)prev=3

Current node: 3

213

DFS Stack

3 (right_done)prev=31 (right_done)prev=3

Return: true

Current node: 1

213

DFS Stack

1 (returning)prev=3

Return: true

213

Return: true

Key Takeaways

✓ Inorder traversal of a BST produces a strictly increasing sequence of node values.

This insight is hard to see from code alone but becomes obvious when watching the traversal order and comparisons.

✓ Tracking the previous node's value during traversal allows efficient validation without extra space.

The visualization shows how a single variable 'prev' is updated and used to check BST property incrementally.

✓ The recursion call stack reflects the traversal path and helps understand how the algorithm backtracks after leaf nodes.

Seeing the call stack states clarifies the recursion flow and why the algorithm returns early on violations.