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

2. Consider the following code snippet for searching a value in a BST. What will be printed when searching for the value 3 in the given tree?

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

def searchBST(root, val):
    current = root
    while current:
        if current.val == val:
            return current
        elif val < current.val:
            current = current.left
        else:
            current = current.right
    return None

root = TreeNode(4, TreeNode(2, TreeNode(1), TreeNode(3)), TreeNode(7))
result = searchBST(root, 3)
print(result.val if result else 'null')

easy

A. 2

B. 7

C. null

D. 3

Solution

1. Step 1: Trace the search path

   Start at root (4). Since 3 < 4, move to left child (2). Since 3 > 2, move to right child (3).

2. Step 2: Check node value

   Current node value is 3, which matches the search value, so return this node.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Search follows BST property correctly and finds node with value 3 [OK]

Hint: Follow BST property to move left or right [OK]

Common Mistakes:

• Returning wrong node value due to off-by-one traversal

3. Given the following code for trimming a BST and the input tree with root value 3, left child 1, right child 4, and low=2, high=3, what is the value of the root node after trimming?

easy

A. 2

B. 3

C. 1

D. 4

Solution

1. Step 1: Move root to valid range

   Root=3 is within [2,3], so no change.

2. Step 2: Trim left subtree

   Left child=1 < 2, so replace left child with its right subtree (None). Left child becomes None.

3. Step 3: Trim right subtree

   Right child=4 > 3, so replace right child with its left subtree (None). Right child becomes None.

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   Root remains 3 with no children after trimming [OK]

Hint: Check root adjustment before subtree trimming [OK]

Common Mistakes:

• Assuming root changes when already in range
• Forgetting to trim subtrees correctly

4. What is the average time complexity per call of next() in the Morris traversal based BST Iterator, assuming the BST has n nodes?

medium

A. O(1) amortized per next() call because each edge is visited at most twice.

B. O(n) per next() call because each call may traverse the entire tree.

C. O(h) per next() call where h is the tree height due to traversing left children.

D. O(log n) per next() call assuming a balanced BST and stack usage.

Solution

1. Step 1: Understand Morris traversal edge visits

   Each edge in the BST is visited at most twice: once to create a thread and once to remove it.

2. Step 2: Calculate amortized cost per next()

   Since total work is O(n) for n nodes, and there are n calls to next(), average cost per call is O(1) amortized.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Amortized O(1) per next() matches Morris traversal properties [OK]

Hint: Morris traversal visits edges twice total [OK]

Common Mistakes:

• Assuming worst-case O(n) per call
• Confusing with stack-based O(h)
• Ignoring amortized analysis

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