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 for a node to be 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 one of the nodes is the ancestor of the other, the ancestor node is the LCA.
Click to reveal answer
intermediate
What is the main idea behind the recursive approach to find LCA in a binary tree?
The recursive approach checks if the current node is one of the target nodes. Then it searches left and right subtrees. If both sides return a node, current node is LCA. If only one side returns a node, that side's node is passed up.
Click to reveal answer
intermediate
Why do we return null when a subtree does not contain any of the target nodes in LCA algorithm?
Returning null means that subtree does not have either of the nodes we are looking for. This helps the parent call know which side contains the nodes and decide the LCA accordingly.
Click to reveal answer
intermediate
What is the time complexity of the standard recursive LCA algorithm in a binary tree?
The time complexity is O(n), where n is the number of nodes in the tree, because in the worst case the algorithm visits every node once.
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.
If one node is ancestor of the other, what is the LCA?
✗ Incorrect
A node is considered a descendant of itself, so the ancestor node is the LCA.
In the recursive LCA algorithm, what does it mean if both left and right recursive calls return non-null?
✗ Incorrect
If both sides return nodes, current node is the lowest node connecting them.
What is returned by the recursive LCA function if neither subtree contains the target nodes?
✗ Incorrect
Null indicates no target nodes found in that subtree.
What is the time complexity of the recursive LCA algorithm in a binary tree with n nodes?
✗ Incorrect
The algorithm visits each node once, so time complexity is O(n).
Explain how the recursive algorithm finds the Lowest Common Ancestor in a binary tree.
Think about how recursion explores left and right children and combines results.
You got /6 concepts.
Describe a real-life analogy to understand the concept of Lowest Common Ancestor.
Imagine tracing back family members to find a shared ancestor.
You got /4 concepts.