Skip to main content
Talentd

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

MediumPremiumFree on FleetCodeHash TableTreeDepth-First SearchBinary Tree8 min readAsked at: Amazon, Meta, Atlassian +1
Practice this problem

Problem Statement

Given the root of a binary tree and an array of TreeNode objects nodes, return the lowest common ancestor (LCA) of all the nodes in nodes. All the nodes will exist in the tree, and all values of the tree's nodes are unique.

Extending the definition of LCA on Wikipedia: "The lowest common ancestor of n nodes p1, p2, ..., pn in a binary tree T is the lowest node that has every pi as a descendant (where we allow a node to be a descendant of itself) for every valid i". A descendant of a node x is a node y that is on the path from node x to some leaf node.

 

Example 1:

Input: root = [3,5,1,6,2,0,8,null,null,7,4], nodes = [4,7]
Output: 2
Explanation: The lowest common ancestor of nodes 4 and 7 is node 2.

Example 2:

Input: root = [3,5,1,6,2,0,8,null,null,7,4], nodes = [1]
Output: 1
Explanation: The lowest common ancestor of a single node is the node itself.

Example 3:

Input: root = [3,5,1,6,2,0,8,null,null,7,4], nodes = [7,6,2,4]
Output: 5
Explanation: The lowest common ancestor of the nodes 7, 6, 2, and 4 is node 5.

 

Constraints:

  • The number of nodes in the tree is in the range [1, 104].
  • -109 <= Node.val <= 109
  • All Node.val are unique.
  • All nodes[i] will exist in the tree.
  • All nodes[i] are distinct.

Approach Overview

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.

Solution

We use a hash table s to record the values of all nodes in the array nodes, and then use depth-first search. When the node being traversed is null or its value is in the hash table s, we return the current node. Otherwise, we recursively traverse the left and right subtrees. If the return values of both the left and right subtrees are not null, it means the current node is the lowest common ancestor. Otherwise, we return the non-null subtree's return value.

The time complexity is O(n + m), and the space complexity is O(n + m). Where n and m are the number of nodes in the binary tree and the length of the array nodes, respectively.

Code

PythonJavaC++JavaScript

Python

Java

C++

JavaScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Repeated Pairwise LCAO(n * k)O(h)When you already have a standard two-node LCA implementation and the number of target nodes is small
Hash Table + DFSO(n)O(k + h)Best general solution; single traversal with constant-time target checks

Video Solution

LOWEST COMMON ANCESTOR OF A BINARY TREE IV | PYTHON | LEETCODE 1676 • Cracking FAANG • 2,587 views views

Watch 8 more video solutions →

Frequently Asked Questions

Is Lowest Common Ancestor of a Binary Tree IV easy or hard?
The problem is generally classified as Medium difficulty. The tree traversal itself is straightforward, but identifying the correct strategy for handling multiple target nodes requires understanding how to aggregate results during DFS.
Lowest Common Ancestor of a Binary Tree IV Python/Java solution
Most implementations follow the same pattern across languages: store nodes in a set and run a recursive DFS that returns the number of targets found in each subtree. Python, Java, C++, and JavaScript versions differ only in syntax while maintaining O(n) time complexity.
How to solve Lowest Common Ancestor of a Binary Tree IV in O(n)?
Insert all target nodes into a hash set, then run a DFS from the root. For each node, recursively count how many targets exist in the left subtree, right subtree, and the current node. When the total equals the number of targets, that node is the LCA. Because the tree is traversed once, the runtime is O(n).
What is the best approach for Lowest Common Ancestor of a Binary Tree IV?
The Hash Table + DFS approach is the most efficient. Store all target nodes in a hash set and perform a single depth-first traversal. Each DFS call returns how many target nodes appear in that subtree. The first node whose subtree contains all targets is the lowest common ancestor. This runs in O(n) time with O(k + h) space.
Is Lowest Common Ancestor of a Binary Tree IV asked at Google/Amazon/Meta?
Lowest Common Ancestor variations are common in interviews at companies like Google, Amazon, and Meta. Interviewers frequently modify the classic two-node LCA problem by adding multiple nodes, parent pointers, or iterative constraints to test deeper tree traversal understanding.
What data structure is used in Lowest Common Ancestor of a Binary Tree IV?
The optimal solution uses a hash table (hash set) to store the target nodes and a depth-first search traversal of the binary tree. The hash set enables constant-time membership checks while DFS aggregates how many targets appear in each subtree.
What is the time complexity of Lowest Common Ancestor of a Binary Tree IV?
The optimal solution runs in O(n) time because each node in the binary tree is visited once during DFS. Hash set lookups for target nodes take O(1). Space complexity is O(k + h), where k is the number of target nodes and h is the tree height due to recursion.

Ready to solve this problem?

Practice Lowest Common Ancestor of a Binary Tree IV with our built-in code editor and test cases.

Practice on FleetCode
Previous

Lowest Common Ancestor of a Binary Search Tree

Next

Lowest Common Ancestor of a Binary Tree