Smallest SubTree With Deepest Nodes in cpp
IntuitionThe goal is to determine the lowest common ancestor (LCA) of the deepest leaves in a binary tree. Here's the thought process:

Calculate the depth of t
# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->
The goal is to determine the lowest common ancestor (LCA) of the deepest leaves in a binary tree. Here's the thought process:

1. Calculate the depth of the left subtree (denoted as x).

2. Similarly, calculate the depth of the right subtree (denoted as y).

Compare the depths:

    If x > y, recursively move to root->left.

    If y > x, recursively move to root->right.

    If x == y, update ans to the current root node (since it serves   as the LCA of the deepest leaves).

4. Finally, return ans.

# Approach
<!-- Describe your approach to solving the problem. -->
This problem can be approached using a post-order traversal to calculate the depth of subtrees and recursively search for the LCA:

1. Define a helper function to calculate the depth of the tree.

2. Implement the main function to compare depths of left and right subtrees and recursively navigate toward the deepest leaves.

3. Update the LCA if the depths are equal.

# Complexity
- Time complexity:
<!-- Add your time complexity here, e.g. $$O(n)$$ -->
$$O(n)$$, where 
𝑛
 is the number of nodes in the tree. We traverse each node once to calculate depths.

- Space complexity:
<!-- Add your space complexity here, e.g. $$O(n)$$ -->
$$O(h)$$, where 
ℎ
 is the height of the tree. This accounts for the recursive stack.

# Code
```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 {
    TreeNode* ans;
    int depth(TreeNode* root)
    {
        if (!root) return -1;
        int DOL = depth(root -> left);
        int DOR = depth(root -> right);

        return max(DOL , DOR) + 1;
    }
public:
    TreeNode* subtreeWithAllDeepest(TreeNode* root) {
        int DOL = depth(root -> left);
        int DOR = depth(root -> right);

        if (DOL > DOR) subtreeWithAllDeepest(root -> left);
        else if (DOR > DOL) subtreeWithAllDeepest(root -> right);
        else ans = root;

        return ans;
    }
};
```
['C++']