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

Source: Dev.to

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).

• Base Case: If a node is null, its depth is 0 and there is no LCA.
• Recursive Step: Query the left and right children for their maximum depths.
  • If the left side is deeper, the deepest nodes are only in the left subtree; propagate the left result upward.
  • If the right side is deeper, the deepest nodes are only in the right subtree; propagate the right result upward.
  • If the depths are equal, the deepest nodes are split between the left and right branches, so 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  // truncated line from original source

Python

class Solution:
    def subtreeWithAllDeepest(self, root):
        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: Process children before the parent, allowing decisions based on complete subtree information.
• Multiple Return Values: Returning both a node and a depth avoids redundant passes, keeping the algorithm efficient.
• LCA Logic: This problem is a variation of the classic lowest common ancestor problem, where the “targets” are defined dynamically by depth rather than by specific values.

Final Thoughts

This problem is a favorite in technical interviews because it tests your ability to handle recursion and complex return types. In practice, the logic mirrors 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.