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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Lowest Common Ancestor of Deepest Leaves

Number: 1218

Difficulty: Medium

Paid? No

Companies: Meta, Google, Amazon

Problem Description

Given the root of a binary tree, find and return the lowest common ancestor (LCA) of its deepest leaves. The deepest leaves are the nodes with the maximum depth from the root. The LCA is defined as the deepest node that is an ancestor of all the deepest leaves.

Key Insights

  • Use a post-order DFS traversal to compute the depth of subtrees.
  • For each node, compare the maximum depths of the left and right subtrees.
  • If both subtrees have the same maximum depth, the current node is the LCA.
  • If one side is deeper, the LCA is in that subtree.

Space and Time Complexity

Time Complexity: O(N) where N is the number of nodes, as every node is visited once. Space Complexity: O(H) where H is the height of the tree, due to the recursion stack.

Solution

We solve the problem using a recursive DFS approach. For every node, we compute two pieces of information:

  1. The deepest depth in its subtree.
  2. The LCA for the deepest leaves in that subtree.

The function works in post-order:

  • If a node is null, it returns a depth of 0.
  • For non-null nodes, recursively compute the deepest depth and LCA from both left and right subtrees.
  • Compare the depths:
    • If left depth is greater, propagate the left LCA.
    • If right depth is greater, propagate the right LCA.
    • If both are equal, the current node is the LCA.

This way, when we backtrack to the root, we have the LCA for all the deepest leaves.

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 lcaDeepestLeaves(self, root: TreeNode) -> TreeNode:
        # Helper function to perform DFS and return a tuple (lca, depth)
        def dfs(node):
            if not node:
                return (None, 0)
            # Recursively compute LCA and depth for left and right subtrees
            left_lca, left_depth = dfs(node.left)
            right_lca, right_depth = dfs(node.right)
            # If left subtree deeper, propagate left LCA
            if left_depth > right_depth:
                return (left_lca, left_depth + 1)
            # If right subtree deeper, propagate right LCA
            elif right_depth > left_depth:
                return (right_lca, right_depth + 1)
            # If depths are equal, current node is the LCA for deepest leaves
            else:
                return (node, left_depth + 1)
        
        # Return only the LCA part from the helper function output
        return dfs(root)[0]
← Back to All Questions