⚡CLEAN CODE⚡| ✅✅BEATS 100%🍨| 🗝️ EASY EXPLANATION🧊 | Using Depth-First-Search
IntuitionGiven 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
# Intuition
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.

This question is same as 1123:[https://leetcode.com/problems/lowest-common-ancestor-of-deepest-leaves/description/]()

# Approach
1. Initialize a treenode res for storing end result and maxDepth initially -1 as global variable.
2. Using function dfs recursively :
* Base Condition : If the root node is pointing null, return maximum of maxDepth and current depth.
* Check for left and right of root node recursively.
* If left is equal to right and maxDepth, we are in the maxDepth so just update res as that root node.
* Else return maximum of left and right node. 

# Complexity
- Time complexity:
O(n)

- Space complexity:
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 {
    TreeNode res;
    int maxDepth=-1;
    public int dfs(TreeNode root,int depth){
        if(root == null){
            maxDepth=Math.max(maxDepth,depth);
            return depth;
        }
        int left=dfs(root.left,depth+1);
        int right=dfs(root.right,depth+1);
        if(left == right && left == maxDepth)res=root;
        return Math.max(left,right);
    }
    public TreeNode subtreeWithAllDeepest(TreeNode root) {
        dfs(root,0);
        return res;
    }
}
```
```c++ []
/**
 * 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 {
    TreeNode* res = nullptr;
    int maxDepth = -1;
    
    int dfs(TreeNode* root, int depth) {
        if (root == nullptr) {
            maxDepth = std::max(maxDepth, depth);
            return depth;
        }
        int left = dfs(root->left, depth + 1);
        int right = dfs(root->right, depth + 1);
        if (left == right && left == maxDepth) {
            res = root;
        }
        return std::max(left, right);
    }

public:
    TreeNode* subtreeWithAllDeepest(TreeNode* root) {
        dfs(root, 0);
        return res;
    }
};
```
```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 __init__(self):
        self.res = None
        self.maxDepth = -1

    def dfs(self, root, depth):
        if not root:
            self.maxDepth = max(self.maxDepth, depth)
            return depth
        left = self.dfs(root.left, depth + 1)
        right = self.dfs(root.right, depth + 1)
        if left == right and left == self.maxDepth:
            self.res = root
        return max(left, right)

    def subtreeWithAllDeepest(self, root: TreeNode) -> TreeNode:
        self.dfs(root, 0)
        return self.res
```
![Upvote.png](https://assets.leetcode.com/users/images/893f120e-d466-498a-bb73-c85eaf0a5b4a_1743757949.9731615.png)

['Tree', 'Depth-First Search', 'Binary Tree', 'C++', 'Java', 'Python3']