LeetCode 1676 - Lowest Common Ancestor of a Binary Tree IV

LeetCode Problem 1676

Difficulty: 🟡 Medium
Topics: Hash Table, Tree, Depth-First Search, Binary Tree

Solution

Problem Understanding

This problem asks us to find the Lowest Common Ancestor, or LCA, of multiple nodes in a binary tree. Unlike the classic LCA problem that involves only two nodes, this variation generalizes the definition to any number of target nodes.

The input consists of:

• root, the root node of a binary tree
• nodes, an array containing references to distinct nodes that exist somewhere in the tree

The goal is to return the single node that is the lowest node in the tree whose subtree contains every node in nodes.

The phrase "lowest common ancestor" is important. A node is considered an ancestor of itself, so if the list contains only one node, that node is automatically its own LCA.

For example, if the target nodes are 4 and 7, their paths upward eventually meet at node 2, so the answer is 2.

The constraints tell us several important things:

• The tree can contain up to 10^4 nodes, so we need an efficient traversal algorithm
• All node values are unique, which allows us to safely identify nodes by value if needed
• Every target node is guaranteed to exist in the tree
• All target nodes are distinct

These guarantees simplify the implementation because we never need to handle invalid or duplicate targets.

Several edge cases are important:

• The nodes array may contain only one node
• One target node may already be an ancestor of all the others
• The LCA may be the root itself
• The target nodes may all lie entirely within one subtree
• The tree may be extremely unbalanced, behaving like a linked list

A naive implementation can easily become inefficient if it repeatedly searches subtrees for each target node. Since the tree size can reach 10^4, we should aim for a linear time solution.

Approaches

Brute Force Approach

A straightforward approach is to compute the ancestor chain for every target node and then compare them.

One way to do this is:

1. Build parent pointers for the entire tree
2. For each target node, walk upward toward the root and record all ancestors
3. Intersect the ancestor sets
4. Find the deepest common ancestor

This approach works because the LCA must appear in the ancestor chain of every target node.

However, this solution introduces unnecessary overhead. We spend extra time building parent mappings and repeatedly traversing upward for every target node. While still acceptable for moderate constraints, it is more complicated and less elegant than necessary.

Optimal DFS Approach

The key insight is that this problem can be solved using the exact same recursive structure as the classic two-node LCA problem.

For any subtree:

• If the current node is one of the targets, we return it
• Otherwise, recursively search the left and right subtrees
• If both sides return non-null values, the current node is the LCA
• If only one side returns a non-null value, propagate that upward

The only difference from the classic problem is that instead of checking whether the current node equals p or q, we check whether it belongs to the set of target nodes.

This works because the first node whose subtree contains targets from multiple branches must be the lowest common ancestor of all target nodes.

Using a hash set for the targets allows constant time membership checks.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(N + KH)	O(N + KH)	Builds parent map and ancestor chains
Optimal	O(N)	O(H + K)	Single DFS traversal with hash set lookup

Where:

• N is the number of nodes in the tree
• K is the number of target nodes
• H is the height of the tree

Algorithm Walkthrough

1. Convert the nodes list into a hash set.

We use a hash set because membership checks become O(1). During DFS, we need to quickly determine whether the current node is one of the targets. 2. Start a depth-first search from the root.

The recursive function explores the tree bottom-up. Each recursive call returns either:

• None, if no target node exists in that subtree
• A target node or LCA candidate, if one exists in that subtree

3. Check whether the current node is a target.

If the current node exists in the target set, immediately return it.

This is important because a target node can itself become the LCA if all other targets lie beneath it. 4. Recursively search the left subtree.

The left recursive call tells us whether any target nodes exist in the left branch. 5. Recursively search the right subtree.

The right recursive call tells us whether any target nodes exist in the right branch. 6. Determine how to propagate results upward.

There are three possibilities:

• Both left and right are non-null

This means target nodes were found in both branches, so the current node is their lowest common ancestor.

• Only one side is non-null

This means all target nodes discovered so far lie within one subtree, so propagate that result upward.

• Both sides are null

This subtree contains no target nodes, so return None. 7. Continue until recursion completes.

The root DFS call eventually returns the overall LCA.

Why it works

The algorithm works because every recursive call summarizes whether its subtree contains any target nodes.

The first node where targets appear in multiple branches must be the lowest node whose subtree contains all targets. Since recursion processes children before parents, the algorithm naturally discovers the lowest valid ancestor before any higher ancestor.

Python Solution

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

from typing import List, Optional

class Solution:
    def lowestCommonAncestor(
        self,
        root: 'TreeNode',
        nodes: 'List[TreeNode]'
    ) -> 'TreeNode':

        target_nodes = set(nodes)

        def dfs(current: Optional['TreeNode']) -> Optional['TreeNode']:
            if current is None:
                return None

            if current in target_nodes:
                return current

            left_result = dfs(current.left)
            right_result = dfs(current.right)

            if left_result and right_result:
                return current

            return left_result if left_result else right_result

        return dfs(root)

The implementation begins by converting the nodes list into a set called target_nodes. This allows constant time membership testing during traversal.

The recursive dfs function processes the tree bottom-up.

The base case handles null nodes by returning None, which indicates that no target node exists in that subtree.

Next, the algorithm checks whether the current node belongs to the target set. If it does, the current node is returned immediately. This allows ancestor relationships among targets to work correctly.

The recursive calls search both subtrees independently.

If both recursive calls return non-null results, the current node must be the lowest node connecting targets from different branches, so it becomes the LCA.

Otherwise, whichever subtree returned a non-null result is propagated upward.

Finally, the original DFS call from the root returns the overall answer.

Go Solution

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */

func lowestCommonAncestor(root *TreeNode, nodes []*TreeNode) *TreeNode {
	targetSet := make(map[*TreeNode]bool)

	for _, node := range nodes {
		targetSet[node] = true
	}

	var dfs func(node *TreeNode) *TreeNode

	dfs = func(node *TreeNode) *TreeNode {
		if node == nil {
			return nil
		}

		if targetSet[node] {
			return node
		}

		leftResult := dfs(node.Left)
		rightResult := dfs(node.Right)

		if leftResult != nil && rightResult != nil {
			return node
		}

		if leftResult != nil {
			return leftResult
		}

		return rightResult
	}

	return dfs(root)
}

The Go implementation follows the same recursive strategy as the Python solution.

Instead of a Python set, Go uses a map[*TreeNode]bool to track target nodes. Since node references are used as keys, membership checks remain constant time.

Go uses nil instead of None for missing nodes. The recursive DFS function returns a *TreeNode pointer, which naturally represents either a valid node or absence of a result.

No integer overflow concerns exist because the algorithm never performs arithmetic on node values.

Worked Examples

Example 1

Input:

root = [3,5,1,6,2,0,8,null,null,7,4]
nodes = [4,7]

Target set:

{4, 7}

Tree structure:

        3
      /   \
     5     1
    / \   / \
   6   2 0   8
      / \
     7   4

DFS traversal:

Current Node	Left Result	Right Result	Returned Value
7	None	None	7
4	None	None	4
2	7	4	2
5	None	2	2
3	2	None	2

Final answer:

2

Example 2

Input:

nodes = [1]

Target set:

{1}

Traversal:

Current Node	Action
1	Node is target, return 1

Since only one node exists in the target list, the node itself is the LCA.

Final answer:

1

Example 3

Input:

nodes = [7,6,2,4]

Target set:

{7,6,2,4}

Traversal summary:

Current Node	Left Result	Right Result	Returned Value
6	None	None	6
7	None	None	7
4	None	None	4
2	7	4	2
5	6	2	5
3	5	None	5

Final answer:

5

Complexity Analysis

Measure	Complexity	Explanation
Time	O(N)	Every node is visited once during DFS
Space	O(H + K)	Recursion stack plus target hash set

The DFS traversal touches each node exactly once, so the total runtime is linear in the size of the tree.

The recursion stack requires O(H) space, where H is the tree height. In the worst case of a completely skewed tree, this becomes O(N).

The target set stores all target nodes, requiring O(K) additional space.

Test Cases

# Definition for testing
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

def build_tree():
    """
            3
          /   \
         5     1
        / \   / \
       6   2 0   8
          / \
         7   4
    """

    nodes = {v: TreeNode(v) for v in [3, 5, 1, 6, 2, 0, 8, 7, 4]}

    nodes[3].left = nodes[5]
    nodes[3].right = nodes[1]

    nodes[5].left = nodes[6]
    nodes[5].right = nodes[2]

    nodes[1].left = nodes[0]
    nodes[1].right = nodes[8]

    nodes[2].left = nodes[7]
    nodes[2].right = nodes[4]

    return nodes[3], nodes

solution = Solution()

# Example 1
root, nodes = build_tree()
assert solution.lowestCommonAncestor(
    root,
    [nodes[4], nodes[7]]
).val == 2  # LCA inside subtree

# Example 2
root, nodes = build_tree()
assert solution.lowestCommonAncestor(
    root,
    [nodes[1]]
).val == 1  # Single node case

# Example 3
root, nodes = build_tree()
assert solution.lowestCommonAncestor(
    root,
    [nodes[7], nodes[6], nodes[2], nodes[4]]
).val == 5  # Multiple nodes under same ancestor

# Root is the LCA
root, nodes = build_tree()
assert solution.lowestCommonAncestor(
    root,
    [nodes[6], nodes[8]]
).val == 3  # Targets split across root

# One target is ancestor of another
root, nodes = build_tree()
assert solution.lowestCommonAncestor(
    root,
    [nodes[5], nodes[4]]
).val == 5  # Ancestor node included in targets

# All targets in left subtree
root, nodes = build_tree()
assert solution.lowestCommonAncestor(
    root,
    [nodes[6], nodes[7], nodes[4]]
).val == 5  # Entirely within one subtree

# Two identical depth leaves
root, nodes = build_tree()
assert solution.lowestCommonAncestor(
    root,
    [nodes[0], nodes[8]]
).val == 1  # Sibling leaves

# Entire tree target set
root, nodes = build_tree()
assert solution.lowestCommonAncestor(
    root,
    list(nodes.values())
).val == 3  # Every node included

Test	Why
[4,7]	Standard subtree LCA case
[1]	Single target node
[7,6,2,4]	Multiple targets across subtree branches
[6,8]	Root becomes LCA
[5,4]	Ancestor node included in targets
[6,7,4]	All targets within one subtree
[0,8]	Sibling leaf nodes
Entire tree	Maximum target coverage

Edge Cases

Single Target Node

If the nodes array contains only one node, the correct answer is that node itself. Some implementations incorrectly continue searching for another matching branch and may accidentally return an ancestor instead.

This implementation handles the case naturally because the DFS immediately returns the node when it appears in the target set.

One Target Is an Ancestor of Others

Suppose the target list contains both node 5 and node 4, where 5 is an ancestor of 4.

A common bug is continuing recursion after discovering node 5, which can incorrectly promote a higher ancestor.

This implementation avoids that problem because target nodes are returned immediately. Once node 5 is found, it propagates upward as the valid LCA.

Root Is the Lowest Common Ancestor

When target nodes lie in completely different branches of the tree, the root itself may be the answer.

For example, nodes 6 and 8 exist in opposite subtrees of root 3.

The algorithm correctly handles this because left and right recursive calls both return non-null values at the root, causing the root to become the LCA.

Highly Unbalanced Tree

A skewed tree behaves like a linked list and can create deep recursion.

The algorithm still works correctly because each node is processed exactly once. The only impact is that recursion depth becomes O(N) instead of O(log N) for balanced trees.