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. The following code attempts to implement a BST Iterator using the Morris traversal technique. Identify the bug that can cause the tree structure to remain corrupted after iteration.

class BSTIterator:
    def __init__(self, root):
        self.current = root
        self.next_val = None
        self._advance()

    def _advance(self):
        while self.current:
            if not self.current.left:
                self.next_val = self.current.val
                self.current = self.current.right
                return
            else:
                pre = self.current.left
                while pre.right and pre.right != self.current:
                    pre = pre.right
                if not pre.right:
                    pre.right = self.current
                    self.current = self.current.left
                else:
                    # BUG: Missing restoration of thread
                    self.next_val = self.current.val
                    self.current = self.current.right

medium

A. Line resetting pre.right to null is missing, so threads are not removed.

B. Line setting self.next_val = self.current.val is incorrect and should be removed.

C. Line moving self.current to self.current.left should be self.current.right instead.

D. Line initializing self.current = root in __init__ is incorrect and should be null.

Solution

1. Step 1: Identify thread restoration step

   In Morris traversal, after visiting a node, the temporary thread (pre.right) must be reset to null to restore the tree.

2. Step 2: Locate missing restoration

   The code omits resetting pre.right = None in the else block, causing the tree to remain modified after iteration.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Missing thread removal corrupts tree structure [OK]

Hint: Always restore threads to avoid tree corruption [OK]

Common Mistakes:

• Forgetting to remove threads
• Misplacing next_val assignment
• Incorrect current pointer updates

2. What is the time complexity of the optimal divide-and-conquer approach to convert a sorted array of length n into a height-balanced BST, and why?

medium

A. O(n log n), because each recursive call processes half the array and builds subtrees.

B. O(n), because each element is visited exactly once to create nodes without extra overhead.

C. O(n^2), because the recursion tree has n levels and each level processes n elements.

D. O(log n), because the tree height is log n and only root nodes are created at each level.

Solution

1. Step 1: Analyze recursion calls

   The algorithm visits each element exactly once to create a TreeNode, splitting the array into halves recursively.

2. Step 2: Calculate total work

   Each element is processed once, so total time is proportional to n.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Single pass over array with divide-and-conquer -> O(n) time [OK]

Hint: Each element processed once -> O(n) time [OK]

Common Mistakes:

• Confusing recursion depth with total work
• Assuming O(n log n) due to recursion

3. What is the worst-case time complexity of inserting a value into a binary search tree using the iterative insertion method shown below?

def insertIntoBST(root, val):
    if root is None:
        return TreeNode(val)
    curr = root
    while 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

medium

A. O(1) because insertion is done at a leaf immediately

B. O(h) where h is the height of the tree, since traversal down the tree is needed

C. O(n) where n is the number of nodes, because all nodes might be visited

D. O(log n) always, because BSTs are balanced by definition

Solution

1. Step 1: Identify traversal cost

   Insertion requires traversing from root down to a leaf where the new node is inserted.

2. Step 2: Relate traversal to tree height

   In worst case, the tree is skewed, so height h can be up to n, but complexity is expressed as O(h).

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Traversal cost dominates insertion -> O(h) [OK]

Hint: Insertion cost depends on tree height, not always balanced [OK]

Common Mistakes:

• Assuming O(1) because insertion is at leaf
• Confusing height h with number of nodes n
• Assuming BST is always balanced

4. Consider the following buggy code snippet for finding the kth smallest element in a BST. Which line contains the subtle bug that can cause incorrect results or runtime errors?

def kthSmallest(root: Optional[TreeNode], k: int) -> int:
    stack = []
    current = root
    count = 0

    while current or stack:
        while current:
            stack.append(current)
            current = current.left
        current = stack.pop()
        count += 1
        if count == k:
            return current.val
        current = current.right

# Bug introduced: k is used as zero-based index (count == k-1) instead of one-based

medium

A. Line with 'if count == k - 1:'

B. Line with 'count += 1'

C. Line with 'stack.append(current)'

D. Line with 'current = current.right'

Solution

1. Step 1: Identify the off-by-one bug

   The condition uses 'count == k - 1' which treats k as zero-based, but k is one-based in problem definition.

2. Step 2: Consequence of bug

   This causes the function to return the (k-1)th smallest element or miss the kth element, leading to incorrect results or runtime errors if k=1.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Correct condition must be 'count == k' to match one-based indexing [OK]

Hint: Check indexing base for k carefully [OK]

Common Mistakes:

• Using zero-based index for k
• Misplacing count increment
• Returning too early

5. What is the time complexity of the optimal solution that uses inorder traversal followed by the two-pointer technique to solve the Two Sum IV in BST problem, assuming the BST has n nodes?

medium

A. O(n log n) due to sorting the inorder traversal array

B. O(n^2) because two-pointer approach checks all pairs in worst case

C. O(n) because inorder traversal and two-pointer scan each take linear time

D. O(log n) because BST properties reduce search space

Solution

1. Step 1: Analyze inorder traversal time

   Inorder traversal visits each node once, O(n) time.

2. Step 2: Analyze two-pointer scan time

   Two pointers move inward at most n steps total, O(n) time.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Both steps are linear, total O(n) time [OK]

Hint: Inorder + two-pointer each O(n), total O(n) [OK]

Common Mistakes:

• Assuming sorting is needed after inorder traversal
• Confusing two-pointer with nested loops
• Thinking BST reduces complexity to log n