Easiest java solution explained | Beats 100%
# IntuitionThe task is to find the subtree with all the deepest nodes in a binary tree. The deepest nodes are the ones that lie at the maximum depth of the tree
### **# Intuition**
The task is to find the **subtree with all the deepest nodes** in a binary tree. The deepest nodes are the ones that lie at the maximum depth of the tree.  
- To solve this, we need to identify the **depth** of the left and right subtrees.
- We then recursively explore the subtree with the deeper depth until we reach the common ancestor of all the deepest nodes.

---

### **# Approach**
1. **Recursive Subtree Traversal:**  
   - Start from the root of the tree and calculate the heights of the left and right subtrees.
   - If the heights are equal, it means the root of the current subtree is the common ancestor of all the deepest nodes, and we can return it.
   - If one side is deeper (greater height), move to that side and repeat the process recursively.

2. **Height Calculation:**  
   - Use a helper function `getHeight()` to calculate the height of a node. The height is defined as the number of edges from the node to the deepest leaf.  
   - For each node, the height is the maximum of the left and right subtree heights, plus one for the current node.

3. **Termination Condition:**  
   - If we reach a leaf node (or a null node), we stop and return the corresponding height (0 for null, 1 for a leaf node).

---

### **# Complexity**
- **Time Complexity:**  
  - For each node, we calculate the height of its subtrees. Since the height calculation involves a traversal of each node, the overall complexity is O(n), where n is the number of nodes in the tree.
  
- **Space Complexity:**  
  - The space complexity is O(h), where h is the height of the tree, because we use recursion (which adds to the stack space).

---

### **# Code Explanation**
```java
class Solution {
    // Function to find the subtree containing all the deepest nodes
    public TreeNode subtreeWithAllDeepest(TreeNode root) {
        if (root == null) {
            return null; // Base case: If root is null, return null
        }
        
        // Calculate the heights of the left and right subtrees
        int leftHeight = getHeight(root.left);
        int rightHeight = getHeight(root.right);

        // If left and right heights are equal, return the current root
        if (leftHeight == rightHeight) {
            return root;
        }
        
        // Otherwise, recurse into the deeper subtree
        if (leftHeight > rightHeight) {
            return subtreeWithAllDeepest(root.left); // Explore left subtree
        } else {
            return subtreeWithAllDeepest(root.right); // Explore right subtree
        }
    }

    // Helper function to calculate the height of a node
    public int getHeight(TreeNode node) {
        if (node == null) {
            return 0; // Base case: height of null node is 0
        }
        // Recursively calculate the height of the left and right subtrees
        return Math.max(getHeight(node.left), getHeight(node.right)) + 1;
    }
}
```

---

### **How the Code Works:**
1. **`subtreeWithAllDeepest()`**:  
   - It first checks the heights of the left and right subtrees using `getHeight()`.
   - If both heights are the same, it means the current node is the common ancestor of all the deepest nodes, so it is returned.
   - If one subtree is deeper than the other, the function recursively calls itself on the deeper side.

2. **`getHeight()`**:  
   - It computes the height of a subtree by returning the maximum depth between the left and right subtrees, incremented by one for the current node.

---

### **Example Run:**
Consider the following binary tree:

```
        1
       / \
      2   3
     / \   \
    4   5   6
        /   / \
       7   8   9
```

- The deepest nodes are `7`, `8`, and `9`, all at level 4.
- The common ancestor of all these nodes is node `3` because it is the root of the subtree that contains all of them.

#### Explanation:
1. The height of the left subtree of node `1` is 3 (`[2, 4]`), and the right subtree is 3 (`[3, 6, 8, 9]`).
2. The left and right heights of node `1` are equal, so the subtree rooted at node `1` contains all the deepest nodes.
3. The result is the subtree rooted at node `1`.

---

### **Key Points:**
- The tree is traversed recursively to find the subtree that includes all the deepest nodes.
- The recursive depth comparisons guide the solution to the correct ancestor node.

#### Thank You !!


['Tree', 'Depth-First Search', 'Binary Tree', 'Java']