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. You need to add a new value into a binary tree such that the tree maintains the property where for every node, all values in the left subtree are smaller and all values in the right subtree are larger. Which approach guarantees this insertion is done correctly and efficiently?

easy

A. Use a breadth-first traversal to find the first empty spot and insert the new value there.

B. Perform an inorder traversal to find the correct position and then insert the new node.

C. Traverse the tree from the root, moving left or right based on comparisons, and insert the new node at the correct leaf position.

D. Use a heap insertion algorithm to maintain the tree structure.

Solution

Solution:

1. Step 1: Understand BST property

   The tree must maintain that left children are smaller and right children are larger than the node.

2. Step 2: Identify insertion method

   Traversing from root and choosing left or right child based on comparison ensures the new value is inserted at the correct leaf position without violating BST properties.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Insertion follows BST ordering rules [OK]

Hint: BST insertion follows value comparisons down the tree [OK]

Common Mistakes:

• Using BFS ignores BST ordering
• Inorder traversal is for traversal, not insertion
• Heap insertion is unrelated to BST

2. What is the worst-case time complexity of the optimized recursive BST node deletion algorithm that uses the in-order successor to replace a node with two children?

medium

A. O(h) where h is the height of the BST

B. O(h^2) due to recursive calls and successor search

C. O(log n) always, since BST is balanced

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

Solution

Solution:

1. Step 1: Identify height-based operations

   Deletion involves searching down the tree (O(h)) and finding the in-order successor, which is also O(h) in worst case.

2. Step 2: Combine operations and recursion

   Successor search and recursive deletion happen along a path of length h, so total time is O(h), not O(h^2).

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Time proportional to tree height, not total nodes or squared height [OK]

Hint: Deletion time depends on tree height, not total nodes [OK]

Common Mistakes:

• Assuming balanced BST always (log n)
• Confusing recursion depth with squared complexity
• Thinking successor search adds extra factor

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

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

4. What is the space complexity of the optimal Morris inorder traversal approach used to recover a BST with two swapped nodes, and why might some candidates mistakenly believe it is higher?

medium

A. O(1) because Morris traversal modifies tree pointers temporarily without extra data structures

B. O(n) due to storing node values during traversal

C. O(h) where h is tree height due to recursion stack in inorder traversal

D. O(log n) because of balanced tree height and implicit stack usage

Solution

Solution:

1. Step 1: Understand Morris traversal space usage

   Morris traversal uses threaded binary tree pointers to traverse without recursion or stack, so no extra space beyond a few pointers.

2. Step 2: Identify common misconception

   Candidates often confuse it with recursive or stack-based inorder traversal, which uses O(h) space, or with storing values in a list, which uses O(n) space.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Morris traversal achieves O(1) space by temporarily modifying tree pointers [OK]

Hint: Morris traversal uses threaded pointers, no stack needed [OK]

Common Mistakes:

• Assuming recursion stack space applies
• Confusing storing values with traversal space
• Believing temporary pointer changes increase space

5. What is the worst-case time complexity of the optimal iterative BST search algorithm when searching for a value in a BST with n nodes and height h?

medium

A. O(log n) always because BSTs are balanced.

B. O(n) because you might have to visit every node in the tree.

C. O(h) because the search path follows the height of the tree.

D. O(1) because the search uses direct indexing.

Solution

Solution:

1. Step 1: Understand BST height and search path

   The search path length is at most the height h of the BST, as each step moves down one level.

2. Step 2: Analyze worst-case time complexity

   In worst case (unbalanced tree), h can be up to n, but complexity is expressed as O(h), not O(n) directly.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Search complexity depends on tree height, not total nodes necessarily [OK]

Hint: Time depends on tree height, not total nodes always [OK]

Common Mistakes:

• Assuming O(log n) always, ignoring unbalanced trees