🔥BEAT 100% with the easiest solution (with explanation) 💯💯
Smallest Subtree with all the Deepest NodesIntuitionThe task is to return the smallest subtree that contains all the deepest nodes of the binary tree.The intuit
# Smallest Subtree with all the Deepest Nodes

## Intuition
The task is to return the smallest subtree that contains all the **deepest** nodes of the binary tree.

The intuition is to:
- Traverse the entire tree to find the maximum depth.
- Use **post-order DFS** to compute the depth of each node’s left and right subtree.
- If both left and right subtree depths are equal and match the **maximum depth**, then this node is the **Lowest Common Ancestor (LCA)** of all deepest nodes.

## Approach
1. Use a recursive DFS function to:
   - Compute and propagate the depth of each subtree.
   - Track the **maximum depth** encountered globally.
   - Update the `lca` variable if the current node’s left and right depths are the same and equal to the maximum depth.
2. Finally, return the node stored in the `lca` variable, which will be the root of the smallest subtree containing all deepest nodes.

## Complexity
- **Time Complexity:** $$O(n)$$ — We visit each node once to compute depths and identify the LCA.
- **Space Complexity:** $$O(h)$$ — Where *h* is the height of the tree due to recursion stack (worst case O(n) for skewed trees).

### If you found this helpful, PLEASE UPVOTE 🥹🥹
![image.png](https://assets.leetcode.com/users/images/5ae74017-84f2-4f09-9621-4cdad251bb0e_1743782746.8609223.png)

## Code

### C++
```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* lca = NULL;
    
    int dfs(TreeNode* root, int depth, int &maxDepth) {
        maxDepth = max(maxDepth, depth);
        if (root == NULL) return depth;

        int leftDepth = dfs(root->left, depth + 1, maxDepth);
        int rightDepth = dfs(root->right, depth + 1, maxDepth);

        int bigDepth = max(leftDepth, rightDepth);

        if (leftDepth == rightDepth && bigDepth == maxDepth) {
            lca = root;
        }

        return bigDepth;
    }

    TreeNode* subtreeWithAllDeepest(TreeNode* root) {
        lca = root;
        int maxDepth = 0;
        dfs(root, 0, maxDepth);
        return lca;
    }
};
```
```python []
class Solution:
    def __init__(self):
        self.lca = None

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

        if left == right and max(left, right) == maxDepth[0]:
            self.lca = root

        return max(left, right)

    def subtreeWithAllDeepest(self, root):
        maxDepth = [0]
        self.dfs(root, 0, maxDepth)
        return self.lca
```
```java []
class Solution {
    TreeNode lca = null;

    public TreeNode subtreeWithAllDeepest(TreeNode root) {
        int[] maxDepth = new int[1];
        dfs(root, 0, maxDepth);
        return lca;
    }

    private int dfs(TreeNode node, int depth, int[] maxDepth) {
        maxDepth[0] = Math.max(maxDepth[0], depth);
        if (node == null) return depth;


        int left = dfs(node.left, depth + 1, maxDepth);
        int right = dfs(node.right, depth + 1, maxDepth);

        if (left == right && Math.max(left, right) == maxDepth[0]) {
            lca = node;
        }

        return Math.max(left, right);
    }
}
```
```javascript []
var subtreeWithAllDeepest = function(root) {
    let lca = null;
    let maxDepth = 0;

    const dfs = (node, depth) => {
        maxDepth = Math.max(maxDepth, depth);
        if (!node) return depth;


        const left = dfs(node.left, depth + 1);
        const right = dfs(node.right, depth + 1);

        if (left === right && Math.max(left, right) === maxDepth) {
            lca = node;
        }

        return Math.max(left, right);
    };

    dfs(root, 0);
    return lca;
};
```
# Summary
- We use a DFS traversal to compute the depth of all nodes.

- By comparing the depths of the left and right subtrees, we detect the node where the deepest leaves meet.

- This solution efficiently returns the smallest subtree that contains all the deepest nodes.


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