100% beats Solution | Java | DFS
IntuitionWe need to return the least common ancestor of the deepest leaves. The deepest leaves are the leaf nodes which are situated at (height of tree - 1)th l
# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->
We need to return the least common ancestor of the deepest leaves. The deepest leaves are the leaf nodes which are situated at (height of tree - 1)th level. Since we need to find the deepest leaves ancestor we can use DFS as it will traverse each branch of tree as deeply as possible. 

The least common ancestor would be one in which both left and right subtree would be able to reach the same level as seen in example 1. It is also clear from example 3, that if a node is single child of its parent, or in other words the depth which each child of a parent can reach are different, then the node would be the least common ancestor.

# Approach
<!-- Describe your approach to solving the problem. -->
We run a DFS over the tree, maintaining the depth we reach when we visit a node. We use post order traversal since it allows us to reach the maximum depth possible in a branch, thus allowing us to find the least common ancestor, when we backtrack upwards in the tree.

Once we reach the end of a branch we check if we have reached the maximum depth we can. If yes, then we update the maximum depth and store the node reached as a possible answer. If we have not gone deeper then the previous maximum depth we reached, that means we can not go any deeper and should now focus on finding least common ancestor. So we check if the maximum depth we can reach from the left and right children are the same. If yes, we have found our least common ancestor and we store it. 

When recursion gets over, we can safely return the least common ancestor we found.

# Complexity
- Time complexity: O(N)
<!-- Add your time complexity here, e.g. $$O(n)$$ -->
We visit each node in tree once.

- Space complexity: O(N)
<!-- Add your space complexity here, e.g. $$O(n)$$ -->
The space the recursion stack takes


# 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 {

    TreeNode answer = null;
    int max_depth = 0;
    public TreeNode lcaDeepestLeaves(TreeNode root) {
        DFS(root, 0);
        return answer;
    }

    private int DFS(TreeNode root, int depth)
    {
        if(root == null)
        return depth - 1;

        // We try to go as deep in the tree as possible
        int leftDepth = DFS(root.left, depth + 1);
        int rightDepth = DFS(root.right, depth + 1);

        // If current depth is the maximum we have reached, then this possibly could be the node we are looking for (if it is single child)
        if(depth > max_depth)
        {
            max_depth = depth;
            answer = root;
        }

        // Other wise we will return the common ancestor which would be node, for which both left depth and right depth would be equal
        else if(leftDepth == rightDepth && leftDepth == max_depth)
        answer = root;

        // We return the maximum of the depths reached
        return Math.max(leftDepth, rightDepth);
    }
}
```
['Tree', 'Depth-First Search', 'Breadth-First Search', 'Binary Tree', 'Java']