Smallest Subtree with all the Deepest Nodes | Beats 100%
IntuitionThe problem requires finding the smallest subtree that contains all the deepest nodes in a binary tree.
The deepest nodes are the ones with the maximum
# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->
The problem requires finding the smallest subtree that contains all the deepest nodes in a binary tree.

- The deepest nodes are the ones with the maximum depth in the tree.
- The smallest subtree means the lowest common ancestor (LCA) of all these deepest nodes.

Our first thought is to traverse the tree and find the deepest nodes' LCA using Depth-First Search (DFS).

# Approach
<!-- Describe your approach to solving the problem. -->
1. Use a DFS helper function that returns a pair containing:
- The node representing the LCA of the deepest nodes.
- The depth of that node.

2. Base Case:
- If the node is null, return (null, 0), meaning no LCA and depth 0.

3. Recursive Case:
- Recursively call DFS on the left and right subtrees.
- Compare the depths of the left and right subtrees:
    - If left depth > right depth, return the left subtree as it contains the LCA.
    - If right depth > left depth, return the right subtree as it contains the LCA.
    - If both depths are equal, return the current node as it is the LCA of the deepest nodes.

4. Final Result:
- The DFS function is called on the root, and the LCA is returned

# Complexity
- Time complexity: O(N)
<!-- Add your time complexity here, e.g. $$O(n)$$ -->

- Space complexity: O(N)
<!-- Add your space complexity here, e.g. $$O(n)$$ -->

# Code
```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();
    }
    public Pair<TreeNode,Integer> dfs(TreeNode root){
        if(root == null)
          return new Pair<>(null,0);
        
        Pair<TreeNode,Integer> left = dfs(root.left);
        Pair<TreeNode,Integer> right = dfs(root.right);

        if(left.getValue() > right.getValue())
          return new Pair<>(left.getKey(),left.getValue()+1);

        if(right.getValue() > left.getValue())
          return new Pair<>(right.getKey(),right.getValue()+1);

        return new Pair(root,left.getValue()+1);
    }
}
```
['Java']