Lowest Common Ancestor in Binary Tree in DSA C++ - Cheat Sheet & Quick Revision

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

beginner

What is the base case when finding LCA recursively in a binary tree?

If the current node is NULL or matches one of the target nodes, return the current node as a potential ancestor.

intermediate

How do you decide the LCA after recursive calls on 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 non-NULL, return that side's result.

intermediate

Why is it important that a node can be a descendant of itself in LCA definition?

Because if one node is ancestor of the other, the LCA is the ancestor node itself, so the function must return that node when found.

beginner

What is the time complexity of finding LCA in a binary tree using a single traversal?

The time complexity is O(n), where n is the number of nodes, because each node is visited once during the recursion.

What should the recursive LCA function return if the current node is NULL?

A NULL

B Current node

C Left child

D Right child

If the current node is NULL, it means no ancestor found in this path, so return NULL.

If the left subtree returns a non-NULL node and the right subtree returns NULL, what does the LCA function return?

A Current node

B NULL

C Right subtree result

D Left subtree result

Only the left subtree has a target node or ancestor, so return that result.

If both left and right recursive calls return non-NULL, what is the LCA?

A Left child

B Right child

C Current node

D NULL

The current node is the lowest node that has both targets in different subtrees.

Can the LCA be one of the nodes itself?

A Yes

B No

C Only if nodes are siblings

D Only if nodes are leaves

If one node is ancestor of the other, it is the LCA.

What is the worst-case time complexity of the LCA algorithm in a binary tree?

A O(log n)

B O(n)

C O(n log n)

D O(1)

The algorithm visits each node once, so time complexity is linear in number of nodes.

Explain the recursive approach to find the Lowest Common Ancestor in a binary tree.

Think about how recursion explores subtrees and combines results.

Describe why the LCA can be one of the nodes itself and how the algorithm handles this case.

Consider when one node is above the other in the tree.