# Smallest Subtree with all the Deepest Nodes
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/smallest-subtree-with-all-the-deepest-nodes)
Canonical: https://scaleengineer.com/dsa/problems/smallest-subtree-with-all-the-deepest-nodes
**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
**Companies:** [Salesforce](https://scaleengineer.com/companies/salesforce)
---
## Problem
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.

**Example 1:**

![](https://assets.glich.co/dsa/smallest-subtree-with-all-the-deepest-nodes/image0.png) 

**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 nodes of the tree.
Notice that nodes 5, 3 and 2 contain the deepest nodes in the tree but node 2 is the smallest subtree among them, so we return it.

**Example 2:**

**Input:** root = [1]
**Output:** [1]
**Explanation:** The root is the deepest node in the tree.

**Example 3:**

**Input:** root = [0,1,3,null,2]
**Output:** [2]
**Explanation:** The deepest node in the tree is 2, the valid subtrees are the subtrees of nodes 2, 1 and 0 but the subtree of node 2 is the smallest.

**Constraints:**

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

**Note:** This question is the same as 1123: <https://leetcode.com/problems/lowest-common-ancestor-of-deepest-leaves/>

# Approaches
## Two-Pass Depth-First Search
This approach solves the problem by breaking it into two distinct phases. First, it traverses the tree to find the maximum depth. Once the maximum depth is known, a second traversal is performed to locate the lowest common ancestor (LCA) of all nodes residing at that depth. This LCA is the root of the smallest subtree containing all deepest nodes.
**Time:** O(N), where N is the number of nodes in the tree. The first pass to find the maximum depth takes O(N) time, and the second pass to find the LCA also takes O(N) time. The total time complexity is O(N) + O(N) = O(N). · **Space:** O(H), where H is the height of the tree. This space is used by the recursion stack. In the worst-case scenario of a skewed tree, H can be equal to N, making the space complexity O(N).
**Pros:** The logic is straightforward and easy to understand as it separates the problem into two simpler subproblems.; The implementation of each pass is a standard tree traversal.
**Cons:** Requires two separate traversals of the entire tree, which is less efficient than a single-pass solution.; Manages state (`maxDepth`) across two different functions, which can be slightly less clean than a self-contained single function.
### Explanation
The first pass is a standard Depth-First Search (DFS) to determine the maximum depth of any node in the tree. We use a helper function that takes a node and its current depth as arguments, and we maintain a global variable `maxDepth` that is updated whenever a greater depth is found. 

After the first pass completes, `maxDepth` holds the depth of the deepest nodes. The second pass also uses a recursive DFS function. This function's goal is to find the LCA of all nodes at `maxDepth`. It works by checking the results from its left and right subtrees. If deepest nodes are found in both subtrees (indicated by non-null return values from both recursive calls), the current node is the LCA. If a node itself is at `maxDepth`, it is considered an LCA for its own subtree. If deepest nodes are only in one subtree, the result from that subtree is passed up the recursion chain. The node returned by the second pass for the root of the tree is the final answer.

```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 {
    private int maxDepth = -1;

    public TreeNode subtreeWithAllDeepest(TreeNode root) {
        // Pass 1: Find the maximum depth of the tree
        findMaxDepth(root, 0);
        // Pass 2: Find the LCA of all nodes at maxDepth
        return findLCA(root, 0);
    }

    private void findMaxDepth(TreeNode node, int depth) {
        if (node == null) {
            return;
        }
        maxDepth = Math.max(maxDepth, depth);
        findMaxDepth(node.left, depth + 1);
        findMaxDepth(node.right, depth + 1);
    }

    private TreeNode findLCA(TreeNode node, int depth) {
        if (node == null) {
            return null;
        }

        // If this node is at the max depth, it's a deepest node.
        if (depth == maxDepth) {
            return node;
        }

        // Recursively search in left and right subtrees.
        TreeNode leftLCA = findLCA(node.left, depth + 1);
        TreeNode rightLCA = findLCA(node.right, depth + 1);

        // If both subtrees contain deepest nodes, the current node is the LCA.
        if (leftLCA != null && rightLCA != null) {
            return node;
        }

        // Otherwise, the LCA must be in the subtree that contains deepest nodes.
        return leftLCA != null ? leftLCA : rightLCA;
    }
}
```
### Algorithm
- **Pass 1: Find Maximum Depth**
  1. Initialize a global variable, `maxDepth`, to -1.
  2. Create a recursive DFS function, `findMaxDepth(node, depth)`, that traverses the tree.
  3. In this function, if the node is null, return. Otherwise, update `maxDepth = Math.max(maxDepth, depth)`.
  4. Recursively call for the left and right children with `depth + 1`.
  5. Start the traversal by calling `findMaxDepth(root, 0)`.
- **Pass 2: Find the Smallest Subtree (LCA)**
  1. Create another recursive function, `findLCA(node, depth)`, that returns a `TreeNode`.
  2. This function performs a post-order traversal. If the current `node` is null, it returns `null`.
  3. If the current `depth` equals the `maxDepth` found in Pass 1, this node is one of the deepest nodes, so return it.
  4. Recursively call `findLCA` for the left and right children: `leftLCA = findLCA(node.left, depth + 1)` and `rightLCA = findLCA(node.right, depth + 1)`.
  5. If both `leftLCA` and `rightLCA` are non-null, it means deepest nodes exist in both subtrees. The current `node` is their lowest common ancestor, so return `node`.
  6. If only one of them is non-null, it means all deepest nodes in this subtree are in that one branch. Propagate the result up by returning the non-null LCA.
  7. If both are null, it means no deepest nodes are in this subtree, so return `null`.
  8. The final answer is the result of `findLCA(root, 0)`.

## Single-Pass Post-Order Traversal
A more efficient approach is to solve the problem in a single pass using a post-order traversal. A recursive helper function can be designed to return two pieces of information for any given subtree: the root of the smallest subtree containing its deepest nodes, and the depth of those nodes. By comparing this information from the left and right children, we can determine the result for the parent node, all in one go.
**Time:** O(N), where N is the number of nodes. 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 skewed tree, this can be O(N) in the worst case.
**Pros:** Highly efficient as it traverses the tree only once.; The logic is self-contained within a single recursive function, leading to more concise code.
**Cons:** The logic can be slightly more complex to reason about compared to a two-pass approach because the recursive function carries more state (both a node and a depth).; Requires a helper class or a pair-like structure to return multiple values from the recursive function.
### Explanation
This method uses a single recursive function, let's call it `dfs`, which performs a post-order traversal. For any node, `dfs` is called on its children first. The function returns a pair of values: `(node, depth)`, where `node` is the LCA of the deepest leaves in the subtree, and `depth` is the depth of those leaves relative to the subtree's root.

When combining results at a parent node, we compare the depths returned from the left and right children. 
- If one child's subtree has a greater depth, it means all the deepest nodes are in that subtree, so we pass its LCA and updated depth upwards.
- If the depths are equal, it means the deepest nodes are spread across both subtrees. In this case, the current node becomes the new LCA. 

This process continues up to the root of the tree, and the final LCA returned for the root is the answer to the problem.

```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 {
    // Helper class to bundle the result: the node and its depth.
    private class Result {
        TreeNode node;
        int depth;

        Result(TreeNode node, int depth) {
            this.node = node;
            this.depth = depth;
        }
    }

    public TreeNode subtreeWithAllDeepest(TreeNode root) {
        return dfs(root).node;
    }

    private Result dfs(TreeNode node) {
        // Base case: an empty subtree has a depth of -1.
        if (node == null) {
            return new Result(null, -1);
        }

        // Post-order traversal: process children first.
        Result leftResult = dfs(node.left);
        Result rightResult = dfs(node.right);

        // The depth of the current node's result is 1 + the depth of its children's result.
        int currentDepth = 1 + Math.max(leftResult.depth, rightResult.depth);

        // Compare depths from left and right subtrees.
        if (leftResult.depth > rightResult.depth) {
            // Deepest nodes are in the left subtree.
            return new Result(leftResult.node, currentDepth);
        } else if (rightResult.depth > leftResult.depth) {
            // Deepest nodes are in the right subtree.
            return new Result(rightResult.node, currentDepth);
        } else {
            // Depths are equal, so the current node is the LCA.
            return new Result(node, currentDepth);
        }
    }
}
```
### Algorithm
1. Define a helper class, `Result`, to store a pair of values: a `TreeNode` and an `int` for depth.
2. Create a recursive DFS function, `dfs(node)`, that returns a `Result` object.
3. **Base Case:** If `node` is null, return a `Result` with a null node and a depth of -1. This serves as the starting point for depth calculation.
4. **Recursive Step:** Perform a post-order traversal. Make recursive calls for the left and right children: `leftResult = dfs(node.left)` and `rightResult = dfs(node.right)`.
5. **Combine Results:**
   - Compare the depths from the left and right results.
   - If `leftResult.depth > rightResult.depth`, the deepest nodes are in the left subtree. Return a new `Result` containing the LCA from the left (`leftResult.node`) and an updated depth (`leftResult.depth + 1`).
   - If `rightResult.depth > leftResult.depth`, the deepest nodes are in the right subtree. Return a new `Result` with the LCA from the right (`rightResult.node`) and updated depth (`rightResult.depth + 1`).
   - If `leftResult.depth == rightResult.depth`, the deepest nodes are in both subtrees (or the current node is a leaf). This means the current `node` is the new LCA. Return a `Result` containing the current `node` and the updated depth (`leftResult.depth + 1`).
6. The final answer is the `node` part of the `Result` returned by the initial call `dfs(root)`.

# Solutions
### 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 subtreeWithAllDeepest ( 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) {} * }; */ using pti = pair < TreeNode * , int > ; class Solution { public: TreeNode * subtreeWithAllDeepest ( TreeNode * root ) { return dfs ( root ). first ; } pti dfs ( TreeNode * root ) { if ( ! root ) return { nullptr , 0 }; pti l = dfs ( root -> left ); pti r = dfs ( root -> right ); int d1 = l . second , d2 = r . second ; if ( d1 > d2 ) return { l . first , d1 + 1 }; if ( d1 < d2 ) return { r . first , 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 subtreeWithAllDeepest ( self , root : TreeNode ) -> 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 ]
```