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 Deepest Leaves

Difficulty: Medium

Problem Description

Given the root of a binary tree, return the lowest common ancestor of its deepest leaves.

Key Insights

  • A leaf node is a node without children.
  • The depth of a node is determined by its distance from the root node.
  • The lowest common ancestor (LCA) of a set of nodes is the deepest node that is an ancestor to all the nodes in that set.
  • The solution requires traversing the tree to find the maximum depth and then determining the LCA of all nodes at that depth.

Space and Time Complexity

Time Complexity: O(N), where N is the number of nodes in the tree, as we may need to visit every node to find the deepest leaves. Space Complexity: O(H), where H is the height of the tree, due to the recursive stack space in depth-first search.

Solution

To solve this problem, we can use a depth-first search (DFS) approach. We will traverse the tree while keeping track of the depth of each node. During the traversal, we will identify the deepest leaves and their corresponding ancestor nodes.

  1. Traverse the tree recursively, maintaining the current depth.
  2. For each node, check if it is a leaf node. If it is, compare its depth with the maximum depth found so far.
  3. If a new maximum depth is found, update the LCA to the current node.
  4. If the current node is at the maximum depth, we will add it to the list of deepest leaves.
  5. Finally, return the LCA of the deepest leaves found during the traversal.

Code Solutions

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def lcaDeepestLeaves(root: TreeNode) -> TreeNode:
    def dfs(node):
        if not node:
            return (0, None)  # (depth, node)
        
        left_depth, left_lca = dfs(node.left)
        right_depth, right_lca = dfs(node.right)
        
        # If left and right depths are equal, this node is the LCA
        if left_depth == right_depth:
            return left_depth + 1, node
        # Otherwise, return the deeper side's information
        return (left_depth + 1, left_lca) if left_depth > right_depth else (right_depth + 1, right_lca)

    return dfs(root)[1]
← Back to All Questions