🌠Beginner-Friendly Guide 'Smallest Subtree with all the Deepest Nodes' – LeetCode 865 (C++, Python, JavaScript)

Navigating binary trees often feels like exploring a maze where you need to keep track of where you are and how deep you have gone. This problem challenges us to not only find the deepest points in that maze but also to find the single lowest meeting point that connects all of them.

---

Problem Summary

You're given:

• The root of a binary tree.
• Nodes at various levels, where the "deepest" nodes are those furthest from the root.

Your goal:

• Find the smallest subtree that contains every single one of those deepest nodes. If there is only one deepest node, that node itself is the answer.

---

Intuition

To solve this, we need to know two things for every node: How deep are its descendants? and Which node is their common ancestor?

We use a recursive Depth First Search (DFS) approach. Instead of just returning a single value, our function returns a pair: the deepest level reached in that subtree and the candidate node for the "Lowest Common Ancestor" (LCA).

1. Base Case: If a node is null, its depth is 0 and there is no LCA.
2. Recursive Step: We ask the left child and the right child for their maximum depths.
3. The Decision:
4. If the Left side is deeper, the deepest nodes are only in the left subtree. We pass the left side's result up to the parent.
5. If the Right side is deeper, the deepest nodes are only in the right subtree. We pass the right side's result up.
6. If the Depths are equal, it means the deepest nodes are split between the left and right branches. In this case, the current node is the "smallest subtree" that joins them.

---

Code Blocks

C++

struct Result {
    TreeNode* lca;
    int depth;
};

class Solution {
public:
    TreeNode* subtreeWithAllDeepest(TreeNode* root) {
        return dfs(root).lca;
    }

private:
    Result dfs(TreeNode* root) {
        if (root == nullptr) return {nullptr, 0};

        Result left = dfs(root->left);
        Result right = dfs(root->right);

        // If one side is deeper, the deepest nodes are exclusively there
        if (left.depth > right.depth) {
            return {left.lca, left.depth + 1};
        }
        if (left.depth < right.depth) {
            return {right.lca, right.depth + 1};
        }

        // If depths are equal, this node is the common ancestor
        return {root, left.depth + 1};
    }
};

Python

class Solution:
    def subtreeWithAllDeepest(self, root: TreeNode) -> TreeNode:
        def dfs(node):
            if not node:
                return None, 0

            left_lca, left_depth = dfs(node.left)
            right_lca, right_depth = dfs(node.right)

            if left_depth > right_depth:
                return left_lca, left_depth + 1
            if right_depth > left_depth:
                return right_lca, right_depth + 1

            # If depths are equal, current node is the LCA
            return node, left_depth + 1

        return dfs(root)[0]

JavaScript

var subtreeWithAllDeepest = function(root) {
    const dfs = (node) => {
        if (!node) return { lca: null, depth: 0 };

        const left = dfs(node.left);
        const right = dfs(node.right);

        if (left.depth > right.depth) {
            return { lca: left.lca, depth: left.depth + 1 };
        }
        if (right.depth > left.depth) {
            return { lca: right.lca, depth: right.depth + 1 };
        }

        // If depths are equal, this node is the common ancestor
        return { lca: node, depth: left.depth + 1 };
    };

    return dfs(root).lca;
};

---

Key Takeaways

• Post-order Traversal: We process the children before the parent. This allows the parent to make decisions based on data gathered from the entire subtree below it.
• Multiple Return Values: By returning both a node and an integer, we avoid redundant passes through the tree, maintaining an efficient time complexity.
• Lowest Common Ancestor (LCA) Logic: This problem is a variation of the classic LCA problem, but the "targets" are defined dynamically by their depth rather than their values.

---

Final Thoughts

This problem is a favorite in technical interviews because it tests your ability to handle recursion and complex return types. In the real world, this logic is similar to finding the "most specific common category" in a database hierarchy or identifying the smallest shared component in a complex dependency tree. Mastering this "bottom-up" information flow is essential for any engineer working with hierarchical data.