Lowest Common Ancestor of a Binary Tree IV - Solution & Explanation

Problem Overview: Given a binary tree and a list of nodes, return their lowest common ancestor (LCA). The LCA is the deepest node in the tree that has all the given nodes as descendants.

This problem extends the classic LCA problem from two nodes to k nodes. Instead of checking two targets, you must detect when the subtree contains all requested nodes and return the deepest node where that happens.

Approach 1: Repeated Pairwise LCA (O(n * k) time, O(h) space)

One straightforward strategy is to reuse the standard two-node LCA algorithm. Start with the LCA of the first two nodes, then compute the LCA of that result with the third node, and continue until all nodes are processed. Each LCA computation requires a full Depth-First Search traversal of the binary tree. While easy to implement if you already know the classic solution, the algorithm becomes inefficient when the number of target nodes grows because the tree may be traversed multiple times.

Approach 2: Hash Table + DFS (O(n) time, O(k + h) space)

This approach solves the problem in a single traversal. First, store all target nodes in a hash table or set for O(1) membership checks. Then perform a DFS starting from the root. Each recursive call returns the number of target nodes found in that subtree.

During DFS, compute left_count and right_count from the children and add 1 if the current node itself is in the target set. When the total count equals the size of the target set for the first time, the current node is the lowest common ancestor. Because each node is visited exactly once and membership checks are constant time, the traversal runs in linear time relative to the number of nodes.

The key insight: instead of searching for specific pairs of nodes, count how many target nodes appear in each subtree. The first node whose subtree contains all targets must be the LCA.

Recommended for interviews: The Hash Table + DFS solution is the expected approach. It demonstrates strong understanding of tree traversal and efficient use of hash sets for membership checks. The pairwise LCA method shows knowledge of the classic problem but is less efficient and rarely preferred when the interviewer expects a single-pass traversal.