We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Lowest Common Ancestor of a Binary Tree IV

Number: 1816

Difficulty: Medium

Paid? Yes

Companies: Amazon

Problem Description

Given the root of a binary tree and an array of TreeNode objects, return the lowest common ancestor (LCA) of all the nodes in the array. A node can be a descendant of itself. All target nodes are guaranteed to be present in the tree and each node value is unique.

Key Insights

  • Use a Depth-First Search (DFS) traversal to explore the tree.
  • Keep track of how many target nodes are found in the subtree rooted at the current node.
  • For each node, sum up the number of target nodes found in the left subtree, right subtree, and the current node.
  • The first (deepest) node in the postorder DFS traversal that reports the total count equal to the number of target nodes is the LCA.
  • Using a HashSet to store the target nodes (or their values) allows O(1) membership checks during traversal.

Space and Time Complexity

Time Complexity: O(n) - We visit each node in the tree once. Space Complexity: O(h) - The recursion stack can grow up to the height of the tree (worst-case O(n) in a skewed tree).

Solution

We solve the problem using a DFS traversal. The idea is to traverse the tree and for each node, count the number of targets present in its left subtree, right subtree, and if the current node itself is a target. When the cumulative count equals the total number of targets and if the LCA has not been found yet, we set the current node as the LCA.

The DFS function returns to its caller the number of target nodes found in the subtree rooted at the current node. Because the DFS recursion is postorder (children processed before the current node), the first time we get a complete match (i.e. all target nodes found) corresponds to the deepest such node, which is by definition the lowest common ancestor.

Data structures used:

  • A set (or hash table) for fast look-up of the target nodes.
  • Recursive call stack to implement DFS.

Code Solutions

# 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:
        # Create a set of target node values for O(1) look-up.
        targets = {node.val for node in nodes}
        # total number of target nodes we need to find.
        self.total = len(targets)
        # answer will hold the LCA node once found.
        self.ans = None

        def dfs(node):
            if not node:
                return 0  # Base case: no target nodes found in an empty subtree.
            # Recursively count targets in the left and right subtrees.
            left_count = dfs(node.left)
            right_count = dfs(node.right)
            # Check if the current node is one of the targets.
            mid_count = 1 if node.val in targets else 0
            # Total targets found in the current subtree.
            total_found = left_count + right_count + mid_count
            # If we found all target nodes in this subtree and haven't recorded an answer yet,
            # mark the current node as the LCA.
            if total_found == self.total and self.ans is None:
                self.ans = node
            # Return the total count to the parent's DFS call.
            return total_found

        dfs(root)
        return self.ans
← Back to All Questions