Lowest Common Ancestor of Deepest Leaves

Problem

As leetcode problem 1123:

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

Recall that:

The node of a binary tree is a leaf if and only if it has no children
The depth of the root of the tree is 0. if the depth of a node is d, the depth of each of its children is d + 1.
The lowest common ancestor of a set S of nodes, is the node A with the largest depth such that every node in S is in the subtree with root A.

As problem 865:

Given the root of a binary tree, the depth of each node is the shortest distance to the root.

Return the smallest subtree such that it contains all the deepest nodes in the original tree.

A node is called the deepest if it has the largest depth possible among any node in the entire tree.

The subtree of a node is a tree consisting of that node, plus the set of all descendants of that node.

Signature:

1
2
3
4
5


class Solution {
    public TreeNode subtreeWithAllDeepest(TreeNode root) {
        
    }
}

Examples

Example 1:

graph TD
    D(3)
    D --- F(5)
    D --- B(1)
    F --- G(6)
    F --- A(2):::orangeYellow
    B --- H(0)
    B --- C(8)
    A --- E(7):::blueShade
    A --- I(4):::blueShade

    classDef orangeYellow fill:#FFD700,stroke:#000,stroke-width:1px,color:#000;
    classDef blueShade fill:#1E90FF,stroke:#000,stroke-width:1px,color:#fff;

1
2
3
4
5


Input: root = [3,5,1,6,2,0,8,null,null,7,4]
Output: [2,7,4]
Explanation: We return the node with value 2, colored in yellow in the diagram.
The nodes coloured in blue are the deepest leaf-nodes of the tree.
Note that nodes 6, 0, and 8 are also leaf nodes, but the depth of them is 2, but the depth of nodes 7 and 4 is 3.

Example 2:

1
2
3


Input: root = [1]
Output: [1]
Explanation: The root is the deepest node in the tree, and it's the lca of itself.

Example 3:

1
2
3


Input: root = [0,1,3,null,2]
Output: [2]
Explanation: The deepest leaf node in the tree is 2, the lca of one node is itself.

Constraints:

The number of nodes in the tree will be in the range [1, 1000].
0 <= Node.val <= 1000
The values of the nodes in the tree are unique.

Note: This question is the same as 865: https://leetcode.com/problems/smallest-subtree-with-all-the-deepest-nodes/

Solution

Method 1 - Postorder Traversal

To solve this, we can perform a bottom-up recursive traversal (post-order traversal), where for each node:

Compute the depth of its left and right subtrees.
If the depths are equal, the current node is the lowest common ancestor of the deepest leaves in its subtree.
If one subtree is deeper, propagate the LCA and depth of that subtree upwards.

This ensures that when recursion reaches the root, we have obtained the LCA of the deepest leaves in the entire tree.

Steps

Use a helper function that returns both the depth and the LCA of the subtree rooted at the current node.
Perform post-order traversal (visit left and right subtree first, then decide the LCA for the current node).

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31


class Solution {
    static class Pair {
        int depth;
        TreeNode lca;

        Pair(int depth, TreeNode lca) {
            this.depth = depth;
            this.lca = lca;
        }        
    }
    public TreeNode lcaDeepestLeaves(TreeNode root) {
        return dfs(root).lca;
    }

    private Pair dfs(TreeNode node) {
        if (node == null) {
            return new Pair(0, null);
        }
        
        Pair left = dfs(node.left);
        Pair right = dfs(node.right);
        
        if (left.depth > right.depth) {
            return new Pair(left.depth + 1, left.lca);
        } else if (right.depth > left.depth) {
            return new Pair(right.depth + 1, right.lca);
        } else {
            return new Pair(left.depth + 1, node);
        }
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


class Solution:
    def lcaDeepestLeaves(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        def dfs(node: Optional[TreeNode]) -> Tuple[int, Optional[TreeNode]]:
            if not node:
                return (0, None)
            
            left_depth, left_lca = dfs(node.left)
            right_depth, right_lca = dfs(node.right)
            
            if left_depth > right_depth:
                return (left_depth + 1, left_lca)
            elif right_depth > left_depth:
                return (right_depth + 1, right_lca)
            else:
                return (left_depth + 1, node)
        
        return dfs(root)[1]

Complexity

⏰ Time complexity: O(n). Traversal of the tree involves visiting all nodes once: O(n).
🧺 Space complexity: O(h). Recursive function stack requires space proportional to the height of the tree: O(h), where h is the height of the tree. In the worst case, for a skewed tree, h = n.

Problem#

Examples#

Solution#

Method 1 - Postorder Traversal#

Steps#

Code#

Complexity#