Want Help Cracking FAANG?

(Then click this)

 ×
Back to Question Bank

1676. Lowest Common Ancestor of a Binary Tree IV - Leetcode Solution

Code Implementation

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

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', nodes: List['TreeNode']) -> 'TreeNode':
        nodes_set = set(nodes)
        
        def dfs(node):
            if not node:
                return None
            if node in nodes_set:
                return node
            left = dfs(node.left)
            right = dfs(node.right)
            if left and right:
                return node
            return left or right
        
        return dfs(root)
      
// Definition for a binary tree node.
// struct TreeNode {
//     int val;
//     TreeNode *left;
//     TreeNode *right;
//     TreeNode() : val(0), left(nullptr), right(nullptr) {}
//     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
//     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
// };

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, vector<TreeNode*>& nodes) {
        unordered_set<TreeNode*> nodeSet(nodes.begin(), nodes.end());
        return dfs(root, nodeSet);
    }
    
    TreeNode* dfs(TreeNode* node, unordered_set<TreeNode*>& nodeSet) {
        if (!node) return nullptr;
        if (nodeSet.count(node)) return node;
        TreeNode* left = dfs(node->left, nodeSet);
        TreeNode* right = dfs(node->right, nodeSet);
        if (left && right) return node;
        return left ? left : right;
    }
};
      
// Definition for a binary tree node.
// public class TreeNode {
//     int val;
//     TreeNode left;
//     TreeNode right;
//     TreeNode() {}
//     TreeNode(int val) { this.val = val; }
//     TreeNode(int val, TreeNode left, TreeNode right) {
//         this.val = val;
//         this.left = left;
//         this.right = right;
//     }
// }

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, List<TreeNode> nodes) {
        Set<TreeNode> nodeSet = new HashSet<>(nodes);
        return dfs(root, nodeSet);
    }
    
    private TreeNode dfs(TreeNode node, Set<TreeNode> nodeSet) {
        if (node == null) return null;
        if (nodeSet.contains(node)) return node;
        TreeNode left = dfs(node.left, nodeSet);
        TreeNode right = dfs(node.right, nodeSet);
        if (left != null && right != null) return node;
        return left != null ? left : right;
    }
}
      
/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */

/**
 * @param {TreeNode} root
 * @param {TreeNode[]} nodes
 * @return {TreeNode}
 */
var lowestCommonAncestor = function(root, nodes) {
    let nodeSet = new Set(nodes);
    function dfs(node) {
        if (!node) return null;
        if (nodeSet.has(node)) return node;
        let left = dfs(node.left);
        let right = dfs(node.right);
        if (left && right) return node;
        return left || right;
    }
    return dfs(root);
};

Problem Description

Given the root of a binary tree, and a list of nodes called nodes (each a reference to a node in the tree), find the lowest common ancestor (LCA) of all the nodes in the list. The lowest common ancestor of a set of nodes is the lowest node in the tree that has all the nodes in the set as descendants (where a node can be a descendant of itself).
  • There is exactly one valid solution.
  • You should not reuse elements in the nodes list; each is a distinct reference.
  • The input root is the root of the given binary tree.
  • The input nodes is a list of TreeNode references (not just values).

Thought Process

To solve this problem, we first recognize that the classic LCA problem is usually for two nodes. Here, we're asked for the LCA of multiple nodes. The brute-force approach would be to find the LCA of the first two nodes, then use that result to find the LCA with the next node, and so on. However, this is not efficient, especially for large trees or large lists of nodes. Instead, we can generalize the recursive LCA algorithm for two nodes to work for a set of nodes. The key insight is: as we traverse the tree, if the current node is one of the targets, we return it. If both left and right subtrees return non-null (i.e., both found at least one target), then the current node is their lowest common ancestor. To speed up the check for whether a node is in the target list, we use a set for O(1) lookups.

Solution Approach

We use a depth-first search (DFS) traversal to solve the problem recursively.
  • 1. Store Targets in a Set: Convert the nodes list into a set for quick lookup.
  • 2. Recursive DFS: For each node:
    • If the node is null, return null.
    • If the node is in the set, return the node itself.
    • Recursively search the left and right children.
    • If both left and right return non-null, this means the current node is the LCA of targets found in each subtree, so return the current node.
    • If only one side returns non-null, propagate that node upward.
  • 3. Initiate DFS from Root: The answer is the result of DFS starting at the root.
Why this works: The recursion ensures that as soon as all target nodes are found in the subtrees, their lowest ancestor is returned up the call stack. The use of a set makes the check for each node efficient.

Example Walkthrough

Suppose the tree is: 
      3
     / \
    5   1
   / \ / \
  6  2 0 8
    / \
   7   4
Let nodes = [5, 1, 4].
  • Start at root (3): not in target set.
  • Left child (5): is in set, so return 5 up.
  • Right child (1): is in set, so return 1 up.
  • Back at root (3): left and right both returned non-null (5 and 1), so 3 is the LCA of 5 and 1.
  • However, need to also check for 4:
  • DFS continues into left subtree (5), then right (2), then right (4): 4 is in set, so return 4 up.
  • Eventually, as the recursion unwinds, the LCA of all three (5, 1, 4) is found to be 3, since that's the lowest node that has all three as descendants.

Time and Space Complexity

  • Brute-force: For each pair, finding LCA takes O(N), and doing this K-1 times for K nodes: O(N*K).
  • Optimized Approach: Each node is visited once during DFS, so time complexity is O(N), where N is the number of nodes in the tree.
  • Space complexity is O(N) for the recursion stack (worst case, skewed tree), and O(K) for the set of targets.

Summary

The solution efficiently finds the lowest common ancestor of multiple nodes in a binary tree by generalizing the classic two-node LCA algorithm. By using a set for O(1) lookups and a recursive DFS traversal, we ensure that the algorithm is both concise and optimal, visiting each node only once and propagating the correct ancestor up the call stack. This approach is elegant because it leverages the structure of the tree and recursion, making the solution clear and efficient.