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.

Practice

1. Consider the following Python code snippet for balancing a BST using inorder traversal and iterative construction. Given the BST with nodes 1, 2, 3 inserted in that order, what is the value of the root node after balancing?

easy

A. 1

B. 2

C. 3

D. None (empty tree)

Solution

1. Step 1: Perform inorder traversal on BST with nodes 1, 2, 3

   Inorder traversal yields nodes in sorted order: [1, 2, 3].

2. Step 2: Iteratively build balanced BST choosing middle node

   Middle index is 1 (0-based), so node with value 2 becomes root.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Middle of [1,2,3] is 2 -> root value 2 [OK]

Hint: Middle element of sorted nodes becomes root [OK]

Common Mistakes:

• Choosing left or right middle always, skewing tree
• Confusing preorder with inorder traversal results
• Forgetting to reset left/right pointers causing cycles

2. Given the following code for inserting a value into a BST, what will be the value of the variable parent.val when inserting 5 into the BST rooted at 4 with left child 2 and right child 7?

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def insertIntoBST(root, val):
    if root is None:
        return TreeNode(val)
    curr = root
    parent = None
    while curr:
        parent = curr
        if val < curr.val:
            if curr.left is None:
                curr.left = TreeNode(val)
                return root
            curr = curr.left
        else:
            if curr.right is None:
                curr.right = TreeNode(val)
                return root
            curr = curr.right
    return root

root = TreeNode(4)
root.left = TreeNode(2)
root.right = TreeNode(7)
val = 5
insertIntoBST(root, val)

easy

A. 4

B. 7

C. 2

D. 5

Solution

1. Step 1: Trace insertion path

   Start at root (4). Since 5 > 4, move right to node 7. Update parent to 4.

2. Step 2: Check right child of 7

   5 < 7, so move left. Left child of 7 is None, so insert here. Parent is now 7, but last parent before insertion was 4.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Parent is last non-null node before insertion -> 4 [OK]

Hint: Parent tracks last node before insertion point [OK]

Common Mistakes:

• Confusing parent with current node
• Off-by-one in loop iteration
• Mistaking inserted value as parent

3. What is the time complexity of the optimal iterative approach that converts a BST to a Greater Tree using reverse inorder traversal with an explicit stack?

medium

A. O(n) where n is the number of nodes in the BST

B. O(n · h) where n is number of nodes and h is tree height

C. O(n · log n) due to stack operations on balanced BST

D. O(h) where h is the height of the BST because each node is visited once

Solution

1. Step 1: Identify number of nodes visited

   Each node is visited exactly once during traversal.

2. Step 2: Analyze stack operations and overall traversal

   While each node is visited once, the explicit stack can hold up to h nodes, and each push/pop operation can be considered O(1). However, in the worst case (unbalanced tree), the height h can be up to n, making the complexity O(n * h).

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Worst-case complexity depends on tree height [OK]

Hint: Worst-case complexity depends on tree height [OK]

Common Mistakes:

• Assuming stack operations multiply complexity by height unnecessarily
• Confusing recursion stack space with time complexity
• Thinking balanced BST implies O(n log n) time

4. Consider the following buggy code for inserting a value into a BST. Which line contains the subtle bug that causes the insertion to fail silently in some cases?

def insertIntoBST(root, val):
    if root is None:
        return TreeNode(val)
    if val < root.val:
        insertIntoBST(root.left, val)
    else:
        insertIntoBST(root.right, val)
    return root

medium

A. Line 2: if root is None

B. Line 4: if val < root.val

C. Line 7: insertIntoBST(root.right, val)

D. Line 5: insertIntoBST(root.left, val)

Solution

1. Step 1: Analyze recursive calls

   Recursive calls to insertIntoBST on root.left or root.right do not update the parent's child pointer.

2. Step 2: Identify missing assignment

   Lines 5 and 7 call insertIntoBST but do not assign the returned subtree back to root.left or root.right, so insertion is lost.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Missing assignment causes silent insertion failure [OK]

Hint: Recursive insert must assign returned subtree to parent's child [OK]

Common Mistakes:

• Not updating parent's child pointer
• Confusing base case with recursive step
• Incorrect comparison operator

5. Suppose the BST can contain negative values and duplicates, and you want to convert it to a Greater Tree where each node's new value is the sum of all nodes with values greater than or equal to it. Which modification to the optimal iterative approach is necessary to handle duplicates correctly?

hard

A. Change traversal to inorder (left-root-right) to process duplicates in ascending order.

B. Use a hash map to store counts of each value and update nodes after traversal.

C. Skip nodes with duplicate values during traversal to avoid double counting.

D. During traversal, accumulate sum including nodes with values equal to current node before updating node value.

Solution

1. Step 1: Understand how duplicates affect sum accumulation

   Duplicates must be included in the sum for nodes with equal values to maintain correctness.

2. Step 2: Modify accumulation logic

   Accumulate sum including all nodes with values >= current node before updating node.val during reverse inorder traversal.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Including equal values in sum ensures correct Greater Tree with duplicates [OK]

Hint: Include equal values in sum during reverse inorder traversal [OK]

Common Mistakes:

• Changing traversal order breaks sum logic
• Skipping duplicates causes incorrect sums
• Using extra data structures unnecessarily increases complexity