MediumHash TableTreeDepth-First SearchBinary TreeBinary LiftingLowest Common AncestorUpdated Sep 2026

1676. Lowest Common Ancestor of a Binary Tree IV

Asked at Atlassian

Difficulty

Medium

Time

O(n)

Space

O(n)

Pattern

Hash Table

Companies

1

Problem

You are given the root of a binary tree and a list of nodes called nodes. Every node in that list really exists in the tree, and every value in the tree is unique.

Return the lowest common ancestor (LCA) of all the nodes in the list. A node x is an ancestor of a node y if y sits on the path going down from x (a node counts as an ancestor of itself). The LCA is the deepest node in the tree that is an ancestor of every node in the list.

If the list has only one node, the answer is that node itself. The answer is always a single node from the tree, so return the node object, not its value.

Find the deepest node covering all targets

657target2answer = 24target3018Node 2 is the lowest node whose subtree holds both targets.
Targets 4 and 7 both hang under node 2, and node 2 is the deepest node that contains both of them.

Constraints

  • ●The number of nodes in the tree is in the range [1, 10^4].
  • ●-10^9 <= Node.val <= 10^9
  • ●All Node.val are unique.
  • ●All nodes[i] will exist in the tree.
  • ●All nodes[i] are distinct.

Examples

Example 1
Inputroot = [3,5,1,6,2,0,8,null,null,7,4], nodes = [4,7]
Output2
WhyNode 4 and node 7 both live under node 2. Node 2 is the deepest node that is an ancestor of both, so it is the LCA.
Example 2
Inputroot = [3,5,1,6,2,0,8,null,null,7,4], nodes = [1]
Output1
WhyWith only one target node, the deepest ancestor of that node is the node itself.
Example 3
Inputroot = [3,5,1,6,2,0,8,null,null,7,4], nodes = [7,6,2,4]
Output5
WhyAll four targets sit inside the subtree of node 5. Node 5 is the deepest node that covers all of them, so it is the answer.

Asked At

1 companies
CompanyDifficulty
AtlassianMediumView all Atlassian questions →

How to Think About It

1

Brute force: check every node and verify if all target nodes exist in its subtree.

2

Use a hash set to store target nodes and return early when a subtree contains them.

3

Post-order traversal: recurse left and right, merging results upward.

4

If both left and right return non-null, current node is the LCA.

5

Optimal: single pass O(n) DFS with a set of targets, returning null if subtree contains zero targets.

Optimal Approach

Perform a depth-first search on the tree. Maintain a set of target nodes. At each node, recurse left and right. If the current node is a target, return it. If both left and right return non-null values, the current node is the LCA. If only one side returns non-null, propagate that result upward. If the current subtree contains fewer targets than the total, return null to signal upward that this subtree is irrelevant. This runs in O(n) time where n is the number of nodes.

Post-order DFS returns targets upward

657returns 724returns 43018Step 1 — the two leaves are targets, so each returns itself.6572left and right both non-null → return 243018Step 2 — node 2 gets a non-null result from both sides, so it is the LCA.target node → return itselfboth children non-null → return current nodeone child non-null → pass it upnone non-null → return null
Each call returns a target found below it, or null. When both children return something, the current node is the LCA.
ComplexityTime O(n)Space O(n)Each node is visited once by the DFS; the space comes from the recursion stack plus the hash set of target nodes.

What Trips People Up in Real Interviews

1

Clarify whether a node can be its own ancestor (yes in this variant).

2

Ask if all nodes are guaranteed to exist in the tree.

3

Mention that a hash set avoids repeated searches for each target node.

4

Explain the post-order pattern: process children before the current node.

5

Discuss how this differs from the classic two-node LCA problem.

Solution Code

O(n) time
class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', nodes: 'List[TreeNode]') -> 'TreeNode':
        targets = set(nodes)
        
        def dfs(node):
            if not node:
                return None
            if node in targets:
                return node
            left = dfs(node.left)
            right = dfs(node.right)
            if left and right:
                return node
            return left if left else right
        
        return dfs(root)

Pro at DSA?

Test your skills with a real FAANG-style mock interview.

Start a Mock Interview →

Frequently Asked Questions

What is the Lowest Common Ancestor of a Binary Tree IV problem?

Given a binary tree and a list of nodes, find the lowest common ancestor of all the given nodes. The LCA is the deepest node that is an ancestor of every node in the list, where a node can be an ancestor of itself.

How do you solve Lowest Common Ancestor of a Binary Tree IV?

The optimal approach runs in O(n) time and O(n) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.

What companies ask Lowest Common Ancestor of a Binary Tree IV?

Lowest Common Ancestor of a Binary Tree IV is asked at Atlassian. It is a medium difficulty problem.

What are common mistakes on Lowest Common Ancestor of a Binary Tree IV?
  • Clarify whether a node can be its own ancestor (yes in this variant).
  • Ask if all nodes are guaranteed to exist in the tree.
  • Mention that a hash set avoids repeated searches for each target node.
  • Explain the post-order pattern: process children before the current node.
  • Discuss how this differs from the classic two-node LCA problem.