Hints That Will Guide You To The Solution Yourself
😇 Actually Good Hints  
  Hint 1.  
  Think about how DFS or finding depth could solve this question?  
  
  Hint 2.  
  Find the maxDepth of the binary tree. T
# 😇 Actually Good Hints  

<details>  
  <summary><span style="font-size:20px;"><strong>Hint 1.</strong></span></summary>  
  <span style="font-size:18px;">Think about how <strong>DFS</strong> or <strong>finding depth</strong> could solve this question?</span>  
</details>  
<br>  

<details>  
  <summary><span style="font-size:20px;"><strong>Hint 2.</strong></span></summary>  
  <span style="font-size:18px;">Find the <strong>maxDepth</strong> of the binary tree. Try solving 
  <a href="https://leetcode.com/problems/maximum-depth-of-binary-tree/" target="_blank">104. Maximum Depth of Binary Tree</a> first if needed.</span>  
</details>
<br>  

<details>  
  <summary><span style="font-size:20px;"><strong>Hint 3.</strong></span></summary>  
  <span style="font-size:18px;">Try to use recursion until you reach <code>maxDepth - 1</code> and return that node.</span>  
</details>  
<br>  

<details>  
  <summary><span style="font-size:20px;"><strong>Hint 4.</strong></span></summary>  
  <span style="font-size:18px;">
    Maintain a <code>currentLength</code> counter during recursion and keep using <strong>DFS</strong> until you reach <code>maxDepth - 1</code>. When you reach that level, you can return the current node:
    <br>
    <code>if (maxi - 1 == currentLength) return root;</code>
    <br>
  </span>  
</details>
<br>

<details>  
  <summary><span style="font-size:20px;"><strong>Hint 5.</strong></span></summary>  
  <span style="font-size:18px;">
    After recursing on both sides, combine their results as follows:
    <br>
    <code>if (left && right) return root;<br>return left ? left : right;</code>
    <br>
    This means if both <strong>left</strong> and <strong>right</strong> return <strong>non-null</strong> values, the <strong>current node</strong> is the <strong>lowest common ancestor</strong>. Otherwise, return the non-null child.
  </span>  
</details>
<br>


</details><br>
<details><summary><span style="font-size:20px;"><strong>Disclaimer [This is the solution]</strong></span></summary> <span style="font-size:18px;"></span>

```cpp []
class Solution {
public:
    TreeNode* subtreeWithAllDeepest(TreeNode* root) {
        int maxi = maxDepth(root); // maxi is the max depth 
        return dfs(root, maxi, 0);
    }

    TreeNode* dfs(TreeNode* root, int maxi, int len) {
        if (!root) return nullptr;  
        if (maxi - 1 == len) return root;
        TreeNode* left = dfs(root->left, maxi, len + 1);
        TreeNode* right = dfs(root->right, maxi, len + 1);
        
        if (left && right) return root;
        return left ? left : right;
    }

    int maxDepth(TreeNode* root) {
        if (!root) return 0;
        return 1 + max(maxDepth(root->left), maxDepth(root->right));
    }
};

```
```Python []
class Solution(object):
    def subtreeWithAllDeepest(self, root) {
        def maxDepth(node):
            if not node:
                return 0
            return 1 + max(maxDepth(node.left), maxDepth(node.right))
        
        def dfs(node, maxi, length):
            if not node:
                return None
            if maxi - 1 == length:
                return node
            left = dfs(node.left, maxi, length + 1)
            right = dfs(node.right, maxi, length + 1)
            if left and right:
                return node
            return left if left else right
        
        maxi = maxDepth(root)  # maxi is the max depth
        return dfs(root, maxi, 0)
```
```Java []
class Solution {
    TreeNode* subtreeWithAllDeepest(TreeNode* root) {
        int maxi = maxDepth(root); // maxi is the max depth
        return dfs(root, maxi, 0);
    }
    
    private TreeNode dfs(TreeNode root, int maxi, int len) {
        if (root == null) return null;
        if (maxi - 1 == len) return root;
        TreeNode left = dfs(root.left, maxi, len + 1);
        TreeNode right = dfs(root.right, maxi, len + 1);
        
        if (left != null && right != null) return root;
        return left != null ? left : right;
    }
    
    private int maxDepth(TreeNode root) {
        if (root == null) return 0;
        return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
    }
}
</details> <br> 

<img src="https://assets.leetcode.com/users/images/cc496d84-0690-4377-b8a3-f621f326df8f_1742786890.68028.png" width="400">
['Tree', 'Breadth-First Search', 'Binary Tree', 'Python', 'C++', 'Java']