# Lowest Common Ancestor of Deepest Leaves
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/lowest-common-ancestor-of-deepest-leaves)
Canonical: https://scaleengineer.com/dsa/problems/lowest-common-ancestor-of-deepest-leaves
**Algorithms:** [Depth-First Search](https://scaleengineer.com/algorithms/depth-first-search), [Breadth-First Search](https://scaleengineer.com/algorithms/breadth-first-search)
**Data structures:** Hash Table, Tree, Binary Tree
---
## Problem
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`.
**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:
# Approaches
## Two-Pass Traversal
This approach tackles the problem by breaking it into two distinct, more straightforward subproblems. First, it performs a full traversal of the tree to identify all the leaf nodes that reside at the maximum possible depth. After collecting these leaves, it initiates a second traversal to find their lowest common ancestor (LCA).
**Time:** O(N). The first pass to find deepest leaves visits every node once, taking O(N) time. The second pass to find the LCA also traverses the tree, taking another O(N) time. The total time complexity is O(N) + O(N) = O(N). · **Space:** O(N). The `deepestLeaves` list can store up to N/2 nodes in the case of a complete binary tree. The recursion stack for both DFS traversals can also reach a depth of H (the tree height), which is O(N) in the worst-case (a skewed tree).
**Pros:** The logic is straightforward as it separates the problem into two well-known tree algorithms: finding nodes at a certain level and finding the LCA of a set of nodes.
**Cons:** Requires two separate traversals of the tree, making it less efficient than a single-pass solution.; Needs extra space to store all the deepest leaf nodes, which can be up to O(N) for a complete binary tree.
### Explanation
This method involves two main passes over the tree.
**Pass 1: Identify the Deepest Leaves**
First, we need to determine the maximum depth of the tree and find all leaf nodes at that depth. This can be done with a single Depth-First Search (DFS) traversal.
- We maintain a global variable `maxDepth` and a list `deepestLeaves`.
- We traverse the tree with a function `findDeepestLeaves(node, depth)`.
- When we encounter a leaf node (`node.left == null && node.right == null`), we check its `depth`.
- If `depth > maxDepth`, we've found a new deepest level. We update `maxDepth`, clear our `deepestLeaves` list, and add the current leaf.
- If `depth == maxDepth`, we've found another leaf at the current maximum depth, so we add it to the list.
**Pass 2: Find the Lowest Common Ancestor (LCA)**
Once we have the set of deepest leaves, we find their LCA.
- If there's only one deepest leaf, it is its own LCA.
- Otherwise, we use a standard LCA-finding algorithm. A recursive function `findLCA(node, targets)` is suitable. We convert our list of leaves to a `Set` for efficient lookups.
- This function returns the `node` itself if it's one of the targets. It recursively checks its left and right subtrees. If it gets non-null results from both children, it means targets exist in both subtrees, making the current `node` the LCA. If only one child returns a result, that result is propagated up.
```java
import java.util.*;
class Solution {
private int maxDepth = -1;
private List deepestLeaves = new ArrayList<>();
public TreeNode lcaDeepestLeaves(TreeNode root) {
// Pass 1: Find the deepest leaves
findDeepestLeaves(root, 0);
// If only one, it's the LCA
if (deepestLeaves.size() == 1) {
return deepestLeaves.get(0);
}
// Pass 2: Find the LCA of the collected leaves
Set targets = new HashSet<>(deepestLeaves);
return findLCA(root, targets);
}
private void findDeepestLeaves(TreeNode node, int depth) {
if (node == null) {
return;
}
if (node.left == null && node.right == null) { // It's a leaf
if (depth > maxDepth) {
maxDepth = depth;
deepestLeaves.clear();
deepestLeaves.add(node);
} else if (depth == maxDepth) {
deepestLeaves.add(node);
}
return;
}
findDeepestLeaves(node.left, depth + 1);
findDeepestLeaves(node.right, depth + 1);
}
private TreeNode findLCA(TreeNode node, Set targets) {
if (node == null || targets.contains(node)) {
return node;
}
TreeNode left = findLCA(node.left, targets);
TreeNode right = findLCA(node.right, targets);
if (left != null && right != null) {
return node;
}
return left != null ? left : right;
}
}
```
### Algorithm
- **Pass 1: Find Deepest Leaves**
1. Initialize `maxDepth = -1` and an empty list `deepestLeaves`.
2. Define a recursive helper function `findDeepestLeaves(node, depth)`.
3. In the helper, if the node is a leaf, compare its `depth` with `maxDepth`. If `depth > maxDepth`, clear the list and add the current leaf. If `depth == maxDepth`, just add the current leaf.
4. Traverse the entire tree by calling `findDeepestLeaves(root, 0)`.
- **Pass 2: Find LCA of Deepest Leaves**
1. If the `deepestLeaves` list contains only one node, return that node as it's the LCA of itself.
2. Create a `Set` of the `deepestLeaves` for efficient O(1) lookups.
3. Define another recursive helper function `findLCA(node, targets)`.
4. In this function, if the current `node` is null or is one of the target leaves, return the `node`.
5. Recursively call `findLCA` for the left and right children.
6. If the calls for both left and right subtrees return a non-null node, it means deepest leaves were found on both sides, making the current `node` the LCA. Return the current `node`.
7. Otherwise, if only one side returned a non-null node, propagate that result up the recursion chain.
8. The initial call `findLCA(root, targets)` will return the final answer.
## One-Pass Post-order Traversal
This optimal approach solves the problem in a single pass using a post-order traversal. For each node, a recursive function computes two key pieces of information: the depth of the deepest leaves in its subtree and the LCA of those leaves. By propagating this information up the tree, we can determine the final LCA at the root level without needing multiple traversals.
**Time:** O(N), where N is the number of nodes in the tree. Each node is visited exactly once during the post-order traversal. · **Space:** O(H), where H is the height of the tree. This space is consumed by the recursion stack. For a balanced tree, this is O(log N), but for a skewed tree, it can be O(N) in the worst case.
**Pros:** Extremely efficient as it solves the problem in a single pass over the tree.; Space-efficient as it does not require storing a list of all deepest leaves.; The code is concise and demonstrates a powerful application of post-order traversal.
**Cons:** The recursive logic, while elegant, can be slightly less intuitive to grasp initially compared to a multi-pass approach.; Requires a helper class or object to return multiple values from the recursive function, which adds a small amount of boilerplate code.
### Explanation
A more efficient solution involves a single Depth-First Search (DFS) using a post-order traversal. The key idea is to have our recursive function return not just one value, but a pair of values for each subtree: the LCA of its deepest leaves and the depth of those leaves.
We can define the depth of a node as its distance to the deepest leaf in its own subtree. A leaf node would have a depth of 0.
The recursive function, say `helper(node)`, would work as follows:
- **Base Case**: If `node` is `null`, it represents an empty subtree. We can return a pair indicating this, for example, `(null, -1)`.
- **Post-order Traversal**: We first make recursive calls on the left and right children to get their results.
- `leftResult = helper(node.left)`
- `rightResult = helper(node.right)`
- **Process Node**: After the recursive calls return, we analyze the results at the current `node`.
- If the left subtree contains deeper leaves (`leftResult.depth > rightResult.depth`), then the overall LCA for the current node's subtree must be the LCA from the left subtree. We pass this information up.
- Similarly, if the right subtree is deeper, the LCA is the one from the right.
- If both subtrees have the same maximum depth (`leftResult.depth == rightResult.depth`), it means the deepest leaves are located in both subtrees. Therefore, the current `node` is the lowest common ancestor for these leaves. We designate the current `node` as the LCA for its subtree.
In each case, the depth returned is `1 +` the depth from the deeper subtree. The final answer is the node returned by the helper function for the root of the tree.
```java
class Solution {
// Helper class to store the result of a subtree traversal: the node and its depth.
class Pair {
TreeNode node;
int depth;
Pair(TreeNode node, int depth) {
this.node = node;
this.depth = depth;
}
}
public TreeNode lcaDeepestLeaves(TreeNode root) {
// The helper function returns a pair, we only need the node part for the final answer.
return helper(root).node;
}
private Pair helper(TreeNode node) {
// Base case: a null node has no leaves.
if (node == null) {
return new Pair(null, -1);
}
// Post-order traversal: process children first.
Pair leftResult = helper(node.left);
Pair rightResult = helper(node.right);
// Compare depths from left and right subtrees to find the LCA.
if (leftResult.depth > rightResult.depth) {
// Deepest leaves are in the left subtree. Propagate the left LCA up.
return new Pair(leftResult.node, leftResult.depth + 1);
} else if (rightResult.depth > leftResult.depth) {
// Deepest leaves are in the right subtree. Propagate the right LCA up.
return new Pair(rightResult.node, rightResult.depth + 1);
} else {
// Depths are equal, so deepest leaves are in both subtrees.
// The current node is the LCA for its subtree.
return new Pair(node, leftResult.depth + 1);
}
}
}
```
### Algorithm
1. Define a helper class, `Pair`, to store two values: the LCA `node` and its `depth` relative to its deepest leaves.
2. Create a recursive helper function `helper(node)` that returns a `Pair`.
3. **Base Case**: If `node` is `null`, return a `Pair(null, -1)` to indicate an empty subtree.
4. **Recursive Step**: Perform a post-order traversal. Recursively call the helper function for the left and right children: `leftResult = helper(node.left)` and `rightResult = helper(node.right)`.
5. **Combine Results**: Compare the depths returned from the children's results.
- If `leftResult.depth > rightResult.depth`, the deepest leaves are all in the left subtree. The LCA is the one from the left. Return a new `Pair(leftResult.node, leftResult.depth + 1)`.
- If `rightResult.depth > leftResult.depth`, the deepest leaves are all in the right subtree. Return a new `Pair(rightResult.node, rightResult.depth + 1)`.
- If `leftResult.depth == rightResult.depth`, the deepest leaves are spread across both subtrees. This means the current `node` is their lowest common ancestor. Return a new `Pair(node, leftResult.depth + 1)`.
6. The main function `lcaDeepestLeaves(root)` initiates the process by calling `helper(root)` and returns the `node` from the resulting `Pair`.
# Solutions
### CSharp
```csharp
/** * Definition for a binary tree node. * public class TreeNode { * public int val; * public TreeNode left; * public TreeNode right; * public TreeNode(int val = 0, TreeNode left = null, TreeNode right = null) { * this.val = val; * this.left = left; * this.right = right; * } * } */ public class Solution { public TreeNode LcaDeepestLeaves ( TreeNode root ) { ( TreeNode , int ) Dfs ( TreeNode root ) { if ( root == null ) { return ( null , 0 ); } var l = Dfs ( root . left ); var r = Dfs ( root . right ); int d1 = l . Item2 ; int d2 = r . Item2 ; if ( d1 > d2 ) { return ( l . Item1 , d1 + 1 ); } if ( d1 < d2 ) { return ( r . Item1 , d2 + 1 ); } return ( root , d1 + 1 ); } return Dfs ( root ). Item1 ; } }
```
### Java
```java
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { public TreeNode lcaDeepestLeaves ( TreeNode root ) { return dfs ( root ). getKey (); } private Pair < TreeNode , Integer > dfs ( TreeNode root ) { if ( root == null ) { return new Pair <>( null , 0 ); } Pair < TreeNode , Integer > l = dfs ( root . left ); Pair < TreeNode , Integer > r = dfs ( root . right ); int d1 = l . getValue (), d2 = r . getValue (); if ( d1 > d2 ) { return new Pair <>( l . getKey (), d1 + 1 ); } if ( d1 < d2 ) { return new Pair <>( r . getKey (), d2 + 1 ); } return new Pair <>( root , d1 + 1 ); } }
```
### CPP
```cpp
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: TreeNode * lcaDeepestLeaves ( TreeNode * root ) { return dfs ( root ). first ; } pair < TreeNode * , int > dfs ( TreeNode * root ) { if ( ! root ) { return { nullptr , 0 }; } auto [ l , d1 ] = dfs ( root -> left ); auto [ r , d2 ] = dfs ( root -> right ); if ( d1 > d2 ) { return { l , d1 + 1 }; } if ( d1 < d2 ) { return { r , d2 + 1 }; } return { root , d1 + 1 }; } };
```
### Python
```python
# 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 : Optional [ TreeNode ]) -> Optional [ TreeNode ]: def dfs ( root ): if root is None : return None , 0 l , d1 = dfs ( root . left ) r , d2 = dfs ( root . right ) if d1 > d2 : return l , d1 + 1 if d1 < d2 : return r , d2 + 1 return root , d1 + 1 return dfs ( root )[ 0 ]
```