Problem Description

You are given the root of a binary tree. Your task is to find the lowest common ancestor (LCA) of all the deepest leaves in the tree.

Let's break down the key concepts:

Leaf nodes: A node is a leaf if it has no children (neither left nor right child).

Depth: The depth of a node represents how far it is from the root. The root has depth 0, its children have depth 1, their children have depth 2, and so on.

Deepest leaves: These are the leaf nodes that are farthest from the root (have the maximum depth among all leaves).

Lowest Common Ancestor (LCA): For a set of nodes, the LCA is the deepest node that has all the nodes in the set as descendants (including the node itself if it's in the set).

Your goal is to find the LCA specifically of all the deepest leaves. This means:

1. First identify which leaves are at the maximum depth
2. Then find the lowest (deepest) node that is an ancestor of all these deepest leaves

For example, if a tree has multiple leaves at depth 4 (and no leaves deeper than that), you need to find the deepest node that is an ancestor of all those depth-4 leaves. This could be:

• The root itself (if the deepest leaves are spread across different subtrees)
• An internal node (if all deepest leaves are within the same subtree)
• A deepest leaf itself (if there's only one deepest leaf)

The function should return the node that serves as the LCA of all deepest leaves.

Flowchart Walkthrough

First, let's pin down the algorithm using the Flowchart. Here's a step-by-step walkthrough:

Is it a graph?

• Yes: A binary tree is a special type of graph where each node has at most two children and there are no cycles.

Is it a tree?

• Yes: The problem explicitly states we're working with a binary tree structure.

DFS

• Yes: According to the flowchart, when we have a tree structure, DFS is the recommended approach.

Conclusion: The flowchart suggests using DFS (Depth-First Search) for this problem.

This makes sense because:

1. We need to explore the entire tree to find all the deepest leaves
2. We need to track depth information as we traverse down the tree
3. We need to compare depths from different subtrees to determine the LCA
4. DFS allows us to process the tree recursively, computing depths bottom-up and determining the LCA based on the depths of left and right subtrees

The DFS approach perfectly aligns with the solution strategy where we recursively traverse the tree, calculate depths for each subtree, and determine the LCA based on comparing these depths. When the depths of left and right subtrees are equal, the current node is the LCA of the deepest leaves in its subtree.

Intuition

The key insight is that we need to find where all the deepest leaves "meet" as we go up the tree. Think of it like finding the lowest junction point where all the deepest paths converge.

When we traverse a tree using DFS, we can calculate the depth of each subtree from bottom to top. As we return from the recursive calls, we have information about the depths of left and right subtrees. This gives us three critical scenarios to consider:

1. Left subtree is deeper than right subtree: All the deepest leaves must be in the left subtree, so the LCA of deepest leaves is also in the left subtree. We can ignore the right subtree entirely.

2. Right subtree is deeper than left subtree: Similarly, all the deepest leaves must be in the right subtree, so the LCA is in the right subtree.

3. Both subtrees have the same depth: This is the interesting case! It means we have deepest leaves in both the left and right subtrees. The current node becomes the meeting point - it's the lowest node that has all these deepest leaves as descendants. Therefore, the current node is the LCA.

The beauty of this approach is that we're essentially "bubbling up" the answer from the bottom of the tree. Each node asks its children: "Who is the LCA of your deepest leaves, and how deep are they?" Based on the answers, it either passes up one of the children's LCAs (if one subtree is deeper) or declares itself as the new LCA (if both subtrees are equally deep).

This naturally handles all cases:

• If there's only one deepest leaf, we keep passing it up until we reach the root
• If all deepest leaves are in one subtree, we pass up that subtree's LCA
• If deepest leaves are spread across both subtrees of a node, that node becomes the LCA

The algorithm elegantly combines depth calculation with LCA finding in a single traversal, making it both efficient and intuitive.

Learn more about Tree, Depth-First Search, Breadth-First Search and Binary Tree patterns.

Solution Approach

The solution implements a DFS approach using a helper function that returns two pieces of information for each node: the LCA candidate and the depth of the subtree.

Helper Function Design:

The dfs(root) function returns a tuple (node, depth) where:

• node is the potential LCA of the deepest leaves in this subtree
• depth is the maximum depth of leaves in this subtree

Base Case:

When we encounter a None node (beyond a leaf), we return (None, 0). This serves as the foundation for our depth calculations.

Recursive Logic:

For each non-null node, we:

1. Recursively explore both subtrees:

   • Call dfs(root.left) to get (l, d1) - the LCA and depth from the left subtree
   • Call dfs(root.right) to get (r, d2) - the LCA and depth from the right subtree

2. Compare depths and determine the LCA:

   • If d1 > d2: The left subtree is deeper, so all deepest leaves are on the left. We return (l, d1 + 1), passing up the left subtree's LCA and incrementing the depth.

   • If d1 < d2: The right subtree is deeper, so all deepest leaves are on the right. We return (r, d2 + 1), passing up the right subtree's LCA and incrementing the depth.

   • If d1 == d2: Both subtrees have the same depth, meaning deepest leaves exist in both subtrees. The current node is their LCA, so we return (root, d1 + 1).

Why increment depth by 1?

As we return from each recursive call, we're moving one level up the tree. The + 1 accounts for the edge between the current node and its child.

Final Result:

The main function calls dfs(root) and extracts the first element of the tuple using [0], which gives us the LCA node.

Time and Space Complexity:

• Time: O(n) where n is the number of nodes, as we visit each node exactly once
• Space: O(h) where h is the height of the tree, for the recursion stack

This elegant solution combines the depth calculation and LCA finding in a single pass, avoiding the need for multiple traversals or additional data structures to store leaf nodes and their depths.

Example Walkthrough

Let's walk through a concrete example to illustrate how the solution works.

Consider this binary tree:

        1
       / \
      2   3
     / \
    4   5

We want to find the LCA of all deepest leaves. The deepest leaves are nodes 4 and 5 (both at depth 2).

Step-by-step DFS traversal:

1. Start at root (1): Call dfs(1)
   • First, recursively call dfs(2) for the left subtree
2. At node 2: Call dfs(2)
   • Recursively call dfs(4) for the left child
3. At node 4 (leaf): Call dfs(4)
   • Call dfs(None) for left child → returns (None, 0)
   • Call dfs(None) for right child → returns (None, 0)
   • Both depths are 0 (equal), so node 4 becomes the LCA
   • Return (4, 1) to node 2
4. Back at node 2: Continue with right child
   • Call dfs(5) for the right child
5. At node 5 (leaf): Call dfs(5)
   • Call dfs(None) for left child → returns (None, 0)
   • Call dfs(None) for right child → returns (None, 0)
   • Both depths are 0 (equal), so node 5 becomes the LCA
   • Return (5, 1) to node 2
6. Back at node 2: Process results from both children
   • Left subtree returned (4, 1) - LCA is node 4, depth is 1
   • Right subtree returned (5, 1) - LCA is node 5, depth is 1
   • Depths are equal (1 == 1), so node 2 becomes the LCA of both deepest leaves
   • Return (2, 2) to node 1
7. Back at root (1): Continue with right child
   • Call dfs(3) for the right subtree
8. At node 3 (leaf): Call dfs(3)
   • Call dfs(None) for left child → returns (None, 0)
   • Call dfs(None) for right child → returns (None, 0)
   • Both depths are 0 (equal), so node 3 becomes the LCA
   • Return (3, 1) to node 1
9. Back at root (1): Process results from both children
   • Left subtree returned (2, 2) - LCA is node 2, depth is 2
   • Right subtree returned (3, 1) - LCA is node 3, depth is 1
   • Left is deeper (2 > 1), so we keep the left subtree's LCA
   • Return (2, 3)

Final Result: The function returns node 2, which is indeed the LCA of the deepest leaves (nodes 4 and 5).

The key moment was at step 6, where node 2 recognized that it had deepest leaves in both its subtrees (both at depth 1 from node 2's perspective) and declared itself as their LCA.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n)

The algorithm performs a depth-first search (DFS) traversal of the binary tree. Each node is visited exactly once during the traversal. At each node, the function performs constant time operations (comparing depths d1 and d2, and returning values). Since we visit all n nodes exactly once and perform O(1) work at each node, the overall time complexity is O(n), where n is the number of nodes in the binary tree.

Space Complexity: O(n)

The space complexity is determined by the recursive call stack. In the worst case, the binary tree is completely unbalanced (e.g., a skewed tree where each node has only one child), resulting in a recursion depth equal to the number of nodes n. This would require O(n) space on the call stack. In the best case of a perfectly balanced tree, the recursion depth would be O(log n), but since we consider worst-case complexity, the space complexity is O(n).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Misunderstanding When to Return Current Node as LCA

The Mistake: A common error is incorrectly determining when the current node should be the LCA. Developers might think that any node with two non-null children should be considered as a potential LCA, leading to code like:

def dfs(node):
    if node is None:
        return None, 0
  
    left_lca, left_depth = dfs(node.left)
    right_lca, right_depth = dfs(node.right)
  
    # WRONG: Just checking if both children exist
    if node.left and node.right:
        return node, max(left_depth, right_depth) + 1
    elif left_depth > right_depth:
        return left_lca, left_depth + 1
    else:
        return right_lca, right_depth + 1

Why It's Wrong: The current node should be the LCA only when deepest leaves exist in BOTH subtrees at the SAME depth. Simply having two children doesn't guarantee that deepest leaves are in both subtrees.

The Fix: Always check if left_depth == right_depth to determine if deepest leaves are distributed across both subtrees:

if left_depth == right_depth:
    return node, left_depth + 1

Pitfall 2: Incorrect Depth Calculation for Leaf Nodes

The Mistake: Some might try to handle leaf nodes as a special case and assign them depth 1 immediately:

def dfs(node):
    if node is None:
        return None, 0
  
    # WRONG: Treating leaf nodes specially
    if node.left is None and node.right is None:
        return node, 1
  
    left_lca, left_depth = dfs(node.left)
    right_lca, right_depth = dfs(node.right)
    # ... rest of logic

Why It's Wrong: This breaks the consistent depth calculation. When a leaf node's children (which are None) return depth 0, adding 1 gives the correct depth of 1 for the leaf. Special-casing leaves can lead to off-by-one errors and makes the logic more complex.

The Fix: Let the recursive logic handle all nodes uniformly. The base case of None returning depth 0 naturally produces the correct depths for all nodes:

# For a leaf node:
# dfs(None) returns (None, 0) for both children
# max(0, 0) + 1 = 1, which is correct for a leaf

Pitfall 3: Forgetting to Handle Single-Node Trees

The Mistake: Not considering that a tree might consist of only a root node (which is also a leaf):

def lcaDeepestLeaves(self, root):
    if not root.left and not root.right:
        # Might forget this case
        pass
    return dfs(root)[0]

Why It's Wrong: A single-node tree is a valid input where the root is the only leaf and thus the LCA of all deepest leaves (itself).

The Fix: The recursive solution naturally handles this case. When the root has no children, both recursive calls return (None, 0), and since depths are equal, the root itself is returned as the LCA:

# For root with no children:
# left_lca, left_depth = None, 0
# right_lca, right_depth = None, 0
# Since 0 == 0, return (root, 1)

Pitfall 4: Confusion About What to Return

The Mistake: Returning the depth instead of the node, or forgetting to extract the node from the tuple:

def lcaDeepestLeaves(self, root):
    # WRONG: Returning the entire tuple
    return dfs(root)
  
    # OR WRONG: Returning the depth
    return dfs(root)[1]

Why It's Wrong: The problem asks for the LCA node itself, not the depth or the tuple containing both.

The Fix: Always extract the first element (the node) from the returned tuple:

return dfs(root)[0]