✅ Easy to Understand & Beginner Friendly | 100% Faster | Detailed Video Explanation🔥
IntuitionThe problem requires finding the Lowest Common Ancestor (LCA) of the deepest leaves in a binary tree.
Since the deepest leaves are the farthest nodes f
# Intuition
The problem requires finding the Lowest Common Ancestor (LCA) of the deepest leaves in a binary tree.  
Since the deepest leaves are the farthest nodes from the root, their LCA must be the node where the left and right subtrees have the same height.  

# Approach
1. **Compute Height:** Define a helper function `height(TreeNode root)` that calculates the height of a subtree.  
2. **Compare Heights:** Recursively compare the heights of the left and right subtrees:
   - If the heights are equal, the current node is the LCA.
   - If the left subtree is taller, the LCA must be in the left subtree.
   - If the right subtree is taller, the LCA must be in the right subtree.  
3. **Recursive Traversal:** Recursively move down towards the deeper subtree until the LCA is found.

# Complexity
- **Time complexity:**  
  - Each call to `lcaDeepestLeaves()` makes two recursive `height()` calls.  
  - The height function runs in $$O(n)$$ and is called multiple times, leading to an overall complexity of **$$O(n^2)$$** in the worst case.
  - This could be optimized using a bottom-up approach with a single traversal.

- **Space complexity:**  
  - In the worst case (skewed tree), the recursion depth can reach **$$O(n)$$** due to the recursive stack.
  - In a balanced tree, the depth is **$$O(\log 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 lcaDeepestLeaves(root);
    }

    /**
     * Finds the Lowest Common Ancestor (LCA) of the deepest leaves in a binary tree.
     * @param root The root node of the binary tree.
     * @return The LCA of the deepest leaves.
     */
    public TreeNode lcaDeepestLeaves(TreeNode root) {
        if (root == null) return null;  // Base case: if tree is empty, return null

        int lh = height(root.left);  // Compute the height of the left subtree
        int rh = height(root.right); // Compute the height of the right subtree

        // If both subtrees have the same height, the current node is the LCA
        if (lh == rh) return root;

        // If left subtree is deeper, move towards left subtree
        if (lh > rh) 
            return lcaDeepestLeaves(root.left);
        
        // Otherwise, move towards right subtree
        return lcaDeepestLeaves(root.right);
    }

    /**
     * Calculates the height of a given binary tree.
     * @param root The root node of the tree.
     * @return The height of the tree.
     */
    private int height(TreeNode root) {
        if (root == null) return 0; // Base case: null node has height 0
        return 1 + Math.max(height(root.left), height(root.right)); // Compute height recursively
    }    
}
```

https://youtu.be/Q9uK_iuJMBw
['Tree', 'Depth-First Search', 'Binary Tree', 'Java']