Lowest Common Ancestor of Deepest Leaves - Video Solutions
Lowest Common Ancestor of Deepest Leaves | Smallest Subtree with all the Deepest Nodes | 1123 | 865
Lowest Common Ancestor of Deepest Leaves - Video Solution
Watch 10 video solutions for Lowest Common Ancestor of Deepest Leaves, a medium level problem involving Hash Table, Tree, Depth-First Search. This walkthrough by codestorywithMIK has 19,362 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Problem Statement
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 isd, the depth of each of its children isd + 1. - The lowest common ancestor of a set
Sof nodes, is the nodeAwith the largest depth such that every node inSis in the subtree with rootA.
Example 1:
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:
Input: root = [1] Output: [1] Explanation: The root is the deepest node in the tree, and it's the lca of itself.
Example 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/
Approach Overview
Problem Overview: Given a binary tree, return the lowest common ancestor (LCA) of all the deepest leaf nodes. The deepest leaves are the nodes located at the maximum depth in the tree. If multiple deepest leaves exist in different subtrees, the answer is the lowest node that is an ancestor of all of them.
Approach 1: Recursive Deepest Leaves and LCA (DFS) (Time: O(n), Space: O(h))
This approach performs a single post-order traversal using Depth-First Search. For every node, compute the depth of its left and right subtrees. If both sides reach the same maximum depth, the current node becomes the lowest common ancestor of the deepest leaves in those subtrees. If one subtree is deeper, propagate the deeper subtree's candidate node upward. Each recursive call returns a pair: the deepest depth found and the corresponding LCA node. Because every node is visited exactly once, the time complexity is O(n). The recursion stack uses O(h) space where h is the tree height. This solution is concise and naturally fits problems involving Tree recursion.
Approach 2: Iterative Deepest Leaves and LCA using BFS (Time: O(n), Space: O(n))
This method first finds all deepest nodes using level-order traversal with Breadth-First Search. Iterate through the tree level by level and track the nodes in the last processed level, which represent the deepest leaves. After collecting these nodes, compute their lowest common ancestor by walking upward using parent references or by repeatedly merging pairs of nodes using an LCA routine on the Binary Tree. BFS guarantees that the final processed level contains exactly the deepest nodes. The traversal visits each node once for O(n) time and stores nodes in a queue with O(n) auxiliary space.
Recommended for interviews: The recursive DFS approach is usually preferred. It solves the problem in a single traversal and directly combines depth computation with LCA discovery. Interviewers expect you to recognize that the deepest leaves determine the LCA based on subtree depths. The BFS approach demonstrates a clear understanding of level traversal and is useful when you explicitly need to identify the deepest level first, but it typically requires extra bookkeeping.
Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Recursive Deepest Leaves + LCA (DFS) | O(n) | O(h) | Best general solution. Single traversal and minimal extra memory. |
| Iterative Deepest Leaves + LCA using BFS | O(n) | O(n) | Useful when explicitly identifying the deepest level first or when avoiding recursion. |