Lowest Common Ancestor in Binary Tree in DSA Go - 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

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

intermediate

What is the base case in the recursive approach to find LCA in a binary tree?

If the current node is null, or if it matches one of the two nodes we are searching for, return the current node.

intermediate

How does the recursive LCA algorithm decide the LCA when both left and right recursive calls return non-null nodes?

If both left and right recursive calls return non-null, it means one node is found in the left subtree and the other in the right subtree, so the current node is their Lowest Common Ancestor.

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.

What does the Lowest Common Ancestor represent in a binary tree?

A The root node of the tree

B The deepest node that is an ancestor of both given nodes

C The node with the smallest value

D The leaf node closest to the root

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 one of the nodes we are searching for?

A Return the current node

B Return the root node

C Return null

D Return the other node

If the current node matches one of the nodes, it is returned as a potential ancestor.

If the left recursive call returns a node and the right recursive call returns null, what does the LCA algorithm return?

A The current node

B The right node

C Null

D The left node

If only one side returns a node, that node is passed up as the ancestor.

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

A O(log n)

B O(1)

C O(n)

D O(n log n)

The algorithm may need to visit every node once, so O(n).

Which of these is NOT true about the Lowest Common Ancestor?

A It is always the root node

B It can be one of the nodes itself

C It is the lowest node with both nodes as descendants

D It can be found using recursion

The LCA is not always the root; it depends on the nodes' positions.

Explain how the recursive algorithm finds the Lowest Common Ancestor in a binary tree.

Think about how recursion explores subtrees and combines results.

Describe a real-life analogy to understand the concept of Lowest Common Ancestor.

Imagine tracing back family members to find a shared grandparent.