LeetCode 865 Solution: Smallest Subtree with Deepest Nodes

Problem Overview

Given the root of a binary tree, we define deepest nodes as the nodes that are at the maximum depth in the tree.
Your task is to return the smallest subtree that contains all of these deepest nodes.

The answer must be a node that is the lowest common ancestor (LCA) of all deepest nodes.

---

Key Observations

1. The deepest nodes lie at the maximum depth of the tree.
2. The smallest subtree that contains all deepest nodes is the lowest node whose subtree includes all of them.
3. This is equivalent to finding the LCA of all deepest nodes.
4. We can compute this efficiently using Depth-First Search (DFS).

---

Strategy

We traverse the tree using DFS and return two values from each node:

• The maximum depth in its subtree
• The node that represents the smallest subtree containing all deepest nodes in that subtree

Core Idea

• If the left subtree is deeper → return left result
• If the right subtree is deeper → return right result
• If both have the same depth → current node is the answer

---

Algorithm (DFS)

For each node:

1. Recursively compute results from left and right children
2. Compare their depths
3. Return:
   • The deeper subtree’s result, or
   • The current node if depths are equal

---

Python Implementation

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

class Solution:
    def subtreeWithAllDeepest(self, root: TreeNode) -> TreeNode:
        
        def dfs(node):
            if not node:
                return (0, None)
            
            left_depth, left_node = dfs(node.left)
            right_depth, right_node = dfs(node.right)
            
            if left_depth > right_depth:
                return (left_depth + 1, left_node)
            elif right_depth > left_depth:
                return (right_depth + 1, right_node)
            else:
                return (left_depth + 1, node)
        
        return dfs(root)[1]

---

Example Walkthrough

Consider this tree:

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

• Deepest nodes: 7 and 4
• Their lowest common ancestor is 2
• Hence, the smallest subtree containing all deepest nodes is rooted at 2

---

Time and Space Complexity

Complexity	Value
Time	O(n) — each node visited once
Space	O(h) — recursion stack (h = tree height)

---

Why This Approach Works Well

• Avoids storing all deepest nodes explicitly
• Computes depth and LCA simultaneously
• Clean, recursive, and optimal

---

Final Thoughts

This problem elegantly combines tree depth computation and lowest common ancestor logic.
By returning both depth and subtree root during DFS, we solve the problem in a single pass—making it both efficient and intuitive.