Finding the Smallest Subtree Containing All Deepest Nodes

When working with binary trees, we often need to identify specific nodes based on their depth. A classic challenge is finding the smallest subtree that contains every single deepest node in the tree.

In this post, we’ll break down the logic, visualize the process, and implement a high-performance solution in Rust.

link to problem: https://leetcode.com/problems/smallest-subtree-with-all-the-deepest-nodes

Understanding the Problem

Imagine a tree where several leaves are at the maximum possible distance from the root.

• If there is only one deepest node, the smallest subtree is just that node itself.

• If there are multiple deepest nodes spread across different branches, the smallest subtree is their Lowest Common Ancestor (LCA).

The Core Logic: Post-Order Traversal

To solve this efficiently, we need two pieces of information from every node:

1. The Maximum Depth: How deep does this specific branch go?

2. The Resulting Node: Which node in this branch is currently the best candidate for the smallest subtree?

As we traverse back up from the leaves (bottom-up), we compare the depths of the left and right children:

• Left Depth > Right Depth: All the deepest nodes are hidden in the left subtree. We pass the left child's candidate up.

• Right Depth > Left Depth: All the deepest nodes are in the right subtree. We pass the right child's candidate up.

• Left Depth == Right Depth: We've found a meeting point. This current node is the common ancestor for the deepest nodes found in both its left and right subtrees. We pass the current node up.

---

Rust Implementation

Rust’s ownership model and Option<Rc<RefCell<T>>> pattern make tree problems interesting. Here is how we implement the recursive depth-tracking solution:

use std::rc::Rc;
use std::cell::RefCell;
use std::cmp::max;

impl Solution {
    pub fn subtree_with_all_deepest(root: Option<Rc<RefCell<TreeNode>>>) -> Option<Rc<RefCell<TreeNode>>> {
        Self::get_depth_and_node(root).1
    }

    // Returns (Depth of this subtree, Smallest subtree containing deepest nodes)
    fn get_depth_and_node(node: Option<Rc<RefCell<TreeNode>>>) -> (i32, Option<Rc<RefCell<TreeNode>>>) {
        match node {
            None => (0, None),
            Some(n) => {
                let (left_depth, left_node) = Self::get_depth_and_node(n.borrow().left.clone());
                let (right_depth, right_node) = Self::get_depth_and_node(n.borrow().right.clone());

                if left_depth > right_depth {
                    (left_depth + 1, left_node)
                } else if right_depth > left_depth {
                    (right_depth + 1, right_node)
                } else {
                    // Depths are equal: this node is the LCA of the deepest nodes in both branches
                    (left_depth + 1, Some(n))
                }
            }
        }
    }
}

Why This Works

The power of this algorithm lies in its time complexity. We only visit each node once. By returning the depth alongside the node, we avoid recalculating the height of the tree multiple times, which would otherwise lead to complexity in a naive implementation.

The space complexity is O(H), where H is the height of the tree, representing the recursion stack.

Conclusion

Finding the smallest subtree containing all deepest nodes is essentially a search for the deepest LCA. By using a bottom-up recursion that bubbles up both depth and node pointers, we can find the answer in a single pass.