LeetCode 865 - Smallest Subtree with all the Deepest Nodes

LeetCode Problem 865

Difficulty: 🟡 Medium
Topics: Hash Table, Tree, Depth-First Search, Breadth-First Search, Binary Tree

Solution

Problem Understanding

The problem gives us the root of a binary tree and asks us to find the smallest subtree that contains all of the deepest nodes in the tree.

The depth of a node is defined as the number of edges between that node and the root. The root itself has depth 0. A deepest node is any node whose depth is equal to the maximum depth present anywhere in the tree.

The important detail is that there may be more than one deepest node. We are not looking for a single deepest node, we are looking for the smallest subtree that contains every deepest node simultaneously.

A subtree rooted at some node includes that node and all of its descendants. Therefore, the answer is effectively the lowest node in the tree whose subtree contains every deepest node.

This problem is equivalent to finding the Lowest Common Ancestor (LCA) of all deepest leaves. If all deepest nodes are located in one branch, the answer may be one of those deepest nodes themselves. If deepest nodes appear in different branches, the answer becomes the node where those branches meet.

The constraints are relatively small, at most 500 nodes, so even less efficient approaches may pass. However, the goal is to design a clean and optimal tree algorithm. The node values are unique, which can help if mappings are needed, although the optimal solution does not require them.

Several edge cases are important:

• A tree with only one node. That node is trivially the deepest node and also the answer.
• A completely skewed tree where every node has only one child. The deepest node itself becomes the answer.
• A balanced tree where deepest nodes exist in both left and right subtrees. The answer becomes a higher ancestor.
• Trees where one subtree is deeper than the other. The answer must come entirely from the deeper side.

Approaches

Brute Force Approach

A brute force solution would first determine the maximum depth in the tree and collect all nodes at that depth. Then, for every node in the tree, we could check whether its subtree contains all deepest nodes.

One possible implementation is:

1. Run DFS or BFS to compute the maximum depth.
2. Collect all deepest nodes.
3. For every node in the tree:

• Traverse its subtree.
• Check whether all deepest nodes are included.

4. Return the smallest valid subtree.

This approach works because it explicitly verifies the definition of the problem. However, it repeatedly traverses subtrees, causing significant redundant work.

If there are N nodes, and for each node we may traverse up to N nodes again, the complexity can degrade to O(N²).

Optimal Approach

The key insight is that the answer depends entirely on subtree depths.

For any node:

• If the left subtree and right subtree have the same maximum depth, then deepest nodes exist in both directions. Therefore, the current node is the smallest subtree containing them all.
• If one subtree is deeper, then all deepest nodes must lie entirely inside that deeper subtree.

This naturally suggests a postorder DFS traversal.

For each node, we return two things:

• The depth of the deepest node in its subtree.
• The subtree root that contains all deepest nodes.

By combining results from the left and right children, we can determine the correct answer for the current node in a single traversal.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(N²)	O(N)	Repeatedly scans subtrees to verify deepest nodes
Optimal	O(N)	O(H)	Single DFS traversal using subtree depth information

H represents the height of the tree.

Algorithm Walkthrough

1. Define a recursive DFS function that processes a subtree and returns two values:

• The node that represents the smallest subtree containing all deepest nodes.
• The depth of the deepest node inside that subtree.

2. Start the recursion from the root. The recursion works in postorder, meaning we process the left subtree, then the right subtree, then the current node.
3. For a null node:

• Return (None, 0).
• A null subtree has depth 0.

4. Recursively process the left child:

• Receive the candidate subtree root from the left side.
• Receive the maximum depth from the left side.

5. Recursively process the right child:

• Receive the candidate subtree root from the right side.
• Receive the maximum depth from the right side.

6. Compare the depths:

• If left_depth > right_depth, then all deepest nodes are inside the left subtree. Return the left candidate and depth left_depth + 1.
• If right_depth > left_depth, then all deepest nodes are inside the right subtree. Return the right candidate and depth right_depth + 1.
• If the depths are equal, deepest nodes exist in both subtrees. The current node becomes the lowest common ancestor of all deepest nodes. Return the current node and depth left_depth + 1.

7. After DFS completes at the root, return the subtree node produced by the recursion.

Why it works

The algorithm maintains an important invariant:

For every subtree, the DFS function returns the smallest subtree containing all deepest nodes within that subtree.

If one side is deeper, every deepest node must lie there, so we propagate that result upward unchanged. If both sides have equal depth, deepest nodes exist in both directions, meaning the current node is the first node that connects them all. That makes it the correct smallest subtree root.

Because every node is processed exactly once and the invariant is maintained recursively, the final answer is correct.

Python Solution

# 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

from typing import Optional, Tuple

class Solution:
    def subtreeWithAllDeepest(
        self,
        root: Optional[TreeNode]
    ) -> Optional[TreeNode]:

        def dfs(node: Optional[TreeNode]) -> Tuple[Optional[TreeNode], int]:
            if not node:
                return None, 0

            left_node, left_depth = dfs(node.left)
            right_node, right_depth = dfs(node.right)

            if left_depth > right_depth:
                return left_node, left_depth + 1

            if right_depth > left_depth:
                return right_node, right_depth + 1

            return node, left_depth + 1

        result, _ = dfs(root)
        return result

The implementation follows the recursive strategy directly.

The dfs function returns a tuple containing:

• The smallest subtree root containing all deepest nodes.
• The maximum depth inside the current subtree.

The base case handles null nodes by returning depth 0.

The recursive calls compute results for the left and right subtrees independently. After both recursive calls finish, the current node compares subtree depths.

If one subtree is deeper, the deepest nodes must all belong to that side, so we propagate its candidate upward.

If both depths are equal, deepest nodes exist in both branches, making the current node their lowest common ancestor. Therefore, the current node becomes the correct subtree root.

Finally, the outer function extracts and returns only the subtree node.

Go Solution

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */

func subtreeWithAllDeepest(root *TreeNode) *TreeNode {

    var dfs func(node *TreeNode) (*TreeNode, int)

    dfs = func(node *TreeNode) (*TreeNode, int) {
        if node == nil {
            return nil, 0
        }

        leftNode, leftDepth := dfs(node.Left)
        rightNode, rightDepth := dfs(node.Right)

        if leftDepth > rightDepth {
            return leftNode, leftDepth + 1
        }

        if rightDepth > leftDepth {
            return rightNode, rightDepth + 1
        }

        return node, leftDepth + 1
    }

    result, _ := dfs(root)
    return result
}

The Go implementation mirrors the Python solution closely.

Go uses multiple return values naturally, which fits this problem well because each DFS call needs to return both a subtree node and a depth.

The base case returns nil for missing nodes. Depth calculations use integers directly, and there are no overflow concerns because the tree contains at most 500 nodes.

Unlike Python tuples, Go explicitly declares the recursive function signature as:

func(node *TreeNode) (*TreeNode, int)

This makes the returned subtree root and depth types explicit.

Worked Examples

Example 1

Input:
        3
      /   \
     5     1
    / \   / \
   6   2 0   8
      / \
     7   4

Deepest nodes are 7 and 4.

We process bottom up.

Node	Left Depth	Right Depth	Returned Node	Returned Depth
6	0	0	6	1
7	0	0	7	1
4	0	0	4	1
2	1	1	2	2
5	1	2	2	3
0	0	0	0	1
8	0	0	8	1
1	1	1	1	2
3	3	2	2	4

Final answer is node 2.

Example 2

Input:
    1

Only one node exists.

Node	Left Depth	Right Depth	Returned Node	Returned Depth
1	0	0	1	1

Final answer is 1.

Example 3

Input:
      0
     / \
    1   3
     \
      2

Deepest node is 2.

Node	Left Depth	Right Depth	Returned Node	Returned Depth
2	0	0	2	1
1	0	1	2	2
3	0	0	3	1
0	2	1	2	3

Final answer is 2.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(N)	Every node is visited exactly once
Space	O(H)	Recursive call stack depends on tree height

The algorithm performs a single DFS traversal. Each node does constant work after processing its children, so the total runtime is linear in the number of nodes.

The space complexity comes from recursion depth. In the worst case of a completely skewed tree, the recursion stack can grow to O(N). In a balanced tree, it becomes O(log N).

Test Cases

# Definition for testing
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):

        def dfs(node):
            if not node:
                return None, 0

            left_node, left_depth = dfs(node.left)
            right_node, right_depth = dfs(node.right)

            if left_depth > right_depth:
                return left_node, left_depth + 1

            if right_depth > left_depth:
                return right_node, right_depth + 1

            return node, left_depth + 1

        return dfs(root)[0]

sol = Solution()

# Example 1
root = TreeNode(3)
root.left = TreeNode(5)
root.right = TreeNode(1)
root.left.left = TreeNode(6)
root.left.right = TreeNode(2)
root.right.left = TreeNode(0)
root.right.right = TreeNode(8)
root.left.right.left = TreeNode(7)
root.left.right.right = TreeNode(4)

assert sol.subtreeWithAllDeepest(root).val == 2  # deepest nodes split across subtree

# Example 2
root = TreeNode(1)

assert sol.subtreeWithAllDeepest(root).val == 1  # single node tree

# Example 3
root = TreeNode(0)
root.left = TreeNode(1)
root.right = TreeNode(3)
root.left.right = TreeNode(2)

assert sol.subtreeWithAllDeepest(root).val == 2  # deepest node itself is answer

# Completely left-skewed tree
root = TreeNode(1)
root.left = TreeNode(2)
root.left.left = TreeNode(3)
root.left.left.left = TreeNode(4)

assert sol.subtreeWithAllDeepest(root).val == 4  # only one deepest node

# Balanced tree with deepest nodes on both sides
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)

assert sol.subtreeWithAllDeepest(root).val == 1  # root is LCA

# Deepest nodes entirely in left subtree
root = TreeNode(1)
root.left = TreeNode(2)
root.left.left = TreeNode(4)
root.right = TreeNode(3)

assert sol.subtreeWithAllDeepest(root).val == 4  # deepest node isolated on left

# Deepest nodes entirely in right subtree
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.right.right = TreeNode(5)

assert sol.subtreeWithAllDeepest(root).val == 5  # deepest node isolated on right

Test	Why
Single node tree	Validates smallest possible input
Balanced tree	Ensures root becomes answer when deepest nodes split
Skewed tree	Ensures deepest node itself can be returned
Deepest nodes in left subtree	Verifies propagation from left side
Deepest nodes in right subtree	Verifies propagation from right side
Complex mixed tree	Tests true lowest common ancestor behavior

Edge Cases

A single-node tree is an important edge case because the root is simultaneously the shallowest and deepest node. Some implementations incorrectly assume at least one child exists and may mishandle recursion termination. This solution correctly returns the root because both subtree depths are equal at 0, making the current node the answer.

A completely skewed tree can expose recursion or depth propagation bugs. In such a tree, every node has only one child, so there is exactly one deepest node. The algorithm correctly keeps propagating the deeper subtree upward until the deepest leaf itself becomes the final answer.

Another subtle edge case occurs when deepest nodes exist in both left and right subtrees at the same depth. A naive implementation might incorrectly return one deepest node instead of their lowest common ancestor. This implementation explicitly checks for equal subtree depths and returns the current node in that situation, guaranteeing the correct smallest subtree is chosen.

A final important case is when one subtree is much deeper than the other. The algorithm must ignore the shallower side entirely. Because the DFS always propagates the deeper subtree upward, the solution naturally handles this case without additional logic.