Lowest Common Ancestor of a BST

▶

Steps

setup

Initialize current node to root

Set the current node pointer to the root of the BST, which has value 6. This is the starting point for the search.

💡 Starting at the root is essential because the BST property allows us to decide direction from here.

Line:

current = root

💡 The search begins at the top of the tree where all values are accessible through BST properties.

compare

Compare p and q with current node value for left subtree

Check if both p (2) and q (8) are less than current node's value (6). They are not, so we do not move left.

💡 This comparison tells us if we should explore the left subtree or not.

Line:

if p.val < current.val and q.val < current.val:

💡 Since both are not less than current, left subtree is not the LCA location.

compare

Compare p and q with current node value for right subtree

Check if both p (2) and q (8) are greater than current node's value (6). They are not, so we do not move right.

💡 This comparison tells us if we should explore the right subtree or not.

Line:

elif p.val > current.val and q.val > current.val:

💡 Since both are not greater than current, right subtree is not the LCA location.

compare

Current node is the Lowest Common Ancestor

Since p and q are on different sides of current node (6), or one equals current, current node is the LCA.

💡 This condition means we found the split point where p and q diverge in the tree.

Line:

else:
    return current

💡 The LCA is the lowest node where p and q are in different subtrees or one matches the node.

reconstruct

Return the LCA node

The algorithm returns the current node (6) as the lowest common ancestor of nodes 2 and 8.

💡 Returning the node completes the search and provides the answer to the problem.

Line:

return current

💡 The search terminates here because the LCA has been found.

reconstruct

Confirm LCA value

The returned node has value 6, which is the lowest common ancestor of nodes 2 and 8.

💡 Confirming the value helps verify the correctness of the algorithm.

Line:

print(lowestCommonAncestor(root, p, q).val)

💡 The LCA value matches the expected output for the given input.

reconstruct

Summary: LCA found at root node

The algorithm confirms that the root node with value 6 is the lowest common ancestor of nodes 2 and 8.

💡 This final summary step reinforces the key insight of the algorithm.

💡 The LCA is the node where the search stops because p and q values split around it.

code_explanation

Code walkthrough: Initialize and loop

The algorithm initializes 'current' to root and enters a loop to traverse the BST.

💡 Understanding the loop structure helps you see how the algorithm progresses step by step.

Line:

current = root  # STEP 1
while current:  # STEP 2

💡 The loop continues until the LCA is found or the tree is fully traversed.

code_explanation

Code walkthrough: Move left or right

If both p and q are less than current, move left; if both greater, move right.

💡 This step shows how the BST property guides the traversal direction.

Line:

if p.val < current.val and q.val < current.val:
    current = current.left
elif p.val > current.val and q.val > current.val:
    current = current.right

💡 The algorithm prunes the search space by moving only in one direction.

code_explanation

Code walkthrough: Found LCA

When p and q split to different sides or match current, return current as LCA.

💡 This final step shows the stopping condition of the algorithm.

Line:

else:
    return current

💡 The LCA is the node where the search stops because p and q diverge.

def lowestCommonAncestor(root, p, q):
    current = root  # STEP 1: Initialize current to root
    while current:  # STEP 2: Loop while current is not None
        if p.val < current.val and q.val < current.val:  # STEP 3: Check if both p and q are less than current
            current = current.left  # STEP 3: Move left
        elif p.val > current.val and q.val > current.val:  # STEP 4: Check if both p and q are greater than current
            current = current.right  # STEP 4: Move right
        else:  # STEP 5: Found split point or match
            return current  # STEP 5: Return current as LCA

# Example usage:
# print(lowestCommonAncestor(root, p, q).val)

📊

Lowest Common Ancestor of a BST - Watch the Algorithm Execute, Step by Step

Watching each step helps you understand how the BST property guides the search efficiently without exploring unnecessary nodes.

Current node: 1

628047935

Current node: 1

628047935

Current node: 1

628047935

Current node: 1

628047935

Return: 1

628047935

Return: 1

628047935

Return: 1

628047935

Return: 1

628047935

Return: 1

628047935

Return: 1

628047935

Return: 1

Key Takeaways

✓ The BST property allows the algorithm to decide direction at each node, drastically reducing search space.

This insight is hard to see from code alone because the efficiency comes from the tree structure, not just the code logic.

✓ The LCA is found at the first node where p and q values split to different subtrees or match the current node.

Understanding this split point is key to grasping why the algorithm stops early.

✓ The algorithm never needs to explore both subtrees fully, making it optimal for BSTs.

This is a concrete example of how BSTs enable efficient queries compared to general binary trees.

Practice

1. Consider the following Python code implementing BST validation using inorder traversal. What is the output of the program when run with the given test cases?

easy

A. true followed by false

B. true followed by true

C. false followed by true

D. false followed by false

Solution

1. Step 1: Trace first tree (2,1,3)

   Inorder traversal yields [1,2,3], strictly increasing, so returns true.

2. Step 2: Trace second tree (5,1,4 with children 3 and 6)

   Inorder traversal yields [1,5,3,4,6], 3 < 5 violates BST property, so returns false.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   First tree valid BST, second invalid due to subtree violation [OK]

Hint: Inorder traversal must be strictly increasing [OK]

Common Mistakes:

• Assuming subtree root comparison is enough
• Confusing output order
• Missing strict inequality check

2. 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

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. What is the time and space complexity of the optimal inorder traversal BST validation algorithm for a tree with n nodes and height h?

medium

A. Time O(n), Space O(h) due to recursion stack where h is tree height

B. Time O(n log n), Space O(n) due to storing all nodes

C. Time O(n^2), Space O(1) because no extra data structures are used

D. Time O(n), Space O(n) because all nodes are stored during traversal

Solution

1. Step 1: Identify time complexity

   The algorithm visits each node exactly once in inorder traversal, so time is O(n).

2. Step 2: Identify space complexity

   Space is O(h) due to recursion stack, where h is the height of the tree; no extra arrays store all nodes.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Linear time and stack space proportional to tree height [OK]

Hint: Inorder traversal visits each node once, stack depth = tree height [OK]

Common Mistakes:

• Confusing recursion stack space with storing all nodes
• Assuming O(n log n) due to sorting
• Ignoring recursion stack space

5. Suppose the BST can contain duplicate values and you want to find the kth smallest element counting duplicates as separate elements. Which modification to the iterative inorder traversal approach correctly handles duplicates without extra space or preprocessing?

hard

A. Perform a full inorder traversal collecting all values, then remove duplicates before indexing kth element.

B. Modify the traversal to skip nodes with duplicate values to avoid counting duplicates multiple times.

C. Use a hash set to track visited values and only increment count for unique values.

D. Keep the traversal unchanged; duplicates are naturally counted separately in inorder traversal order.

Solution

1. Step 1: Understand duplicates in BST inorder traversal

   Inorder traversal visits nodes in sorted order including duplicates as separate nodes.

2. Step 2: Check if modification is needed

   Since duplicates appear as separate nodes, counting each node visited naturally counts duplicates separately without extra logic.

3. Step 3: Evaluate other options

   Skipping duplicates (B) or using a hash set (C) changes semantics. Removing duplicates after full traversal (D) is inefficient and breaks counting duplicates separately.

4. Final Answer:

   Option D -> Option D

5. Quick Check:

   Inorder traversal inherently counts duplicates separately [OK]

Hint: Duplicates appear as separate nodes in inorder traversal [OK]

Common Mistakes:

• Trying to skip duplicates
• Using extra space unnecessarily
• Assuming duplicates must be merged