Recall & Review
beginner
What is the Lowest Common Ancestor (LCA) in a binary tree?
The Lowest Common Ancestor of two nodes in a binary tree is the deepest (lowest) node that has both nodes as descendants (where a node can be a descendant of itself).
Click to reveal answer
beginner
In the context of LCA, what does it mean if a node is a descendant of itself?
It means that when checking if a node is a descendant of another, the node itself counts as its own descendant. So if the node is one of the two nodes we are finding LCA for, it can be the LCA.
Click to reveal answer
intermediate
What is the base case in a recursive LCA function for a binary tree?
If the current node is null, or if it matches one of the two target nodes, return the current node.
Click to reveal answer
intermediate
How does the recursive LCA function decide the LCA after exploring left and right subtrees?
If both left and right recursive calls return non-null nodes, the current node is the LCA. If only one side returns a non-null node, that node is returned up the recursion.
Click to reveal answer
intermediate
Why does the LCA algorithm work even if one node is ancestor of the other?
Because the algorithm returns the node itself if it matches one of the target nodes, so if one node is ancestor of the other, it will be returned as LCA.
Click to reveal answer
What does the Lowest Common Ancestor represent in a binary tree?
✗ Incorrect
The LCA is the deepest node that has both nodes as descendants.
In the recursive LCA algorithm, what should be returned if the current node is null?
✗ Incorrect
If the current node is null, return null to indicate no target found here.
If the left recursive call returns a node and the right recursive call returns null, what does the LCA function return?
✗ Incorrect
Return the non-null node from the left side up the recursion.
What happens if one of the target nodes is the ancestor of the other in the LCA algorithm?
✗ Incorrect
The algorithm returns the ancestor node because it matches one of the targets.
Which traversal method is implicitly used in the recursive LCA algorithm?
✗ Incorrect
The algorithm explores left and right children first, then processes the current node, which is postorder.
Explain how the recursive Lowest Common Ancestor algorithm works in a binary tree.
Think about how recursion explores children and combines results.
You got /4 concepts.
Describe why the Lowest Common Ancestor algorithm correctly handles the case when one node is ancestor of the other.
Consider what happens when the recursion hits a target node.
You got /4 concepts.