Lowest Common Ancestor of Deepest Leaves

medium binary tree dfs post-order

Problem

Given the root of a binary tree, return the lowest common ancestor of its deepest leaves. The deepest leaves are all the leaves at the maximum depth of the tree, and a node is a common ancestor of a set of nodes if every node in the set is in the subtree rooted at that node.

Inputroot = [3, 5, 1, 6, 2, 0, 8, null, null, 7, 4]

Output2

The deepest leaves are 7 and 4 (depth 3). Their lowest common ancestor is node 2.

tree (level-order, comma-separated, use null)

def lcaDeepestLeaves(root):
    def dfs(node):
        if not node:
            return 0, None
        ld, ll = dfs(node.left)
        rd, rl = dfs(node.right)
        if ld == rd:
            return ld + 1, node
        return (ld + 1, ll) if ld > rd else (rd + 1, rl)
    return dfs(root)[1]

function lcaDeepestLeaves(root) {
  function dfs(node) {
    if (!node) return [0, null];
    const [ld, ll] = dfs(node.left);
    const [rd, rl] = dfs(node.right);
    if (ld === rd) return [ld + 1, node];
    return ld > rd ? [ld + 1, ll] : [rd + 1, rl];
  }
  return dfs(root)[1];
}

class Solution {
    private int maxDepth = -1;
    private TreeNode ans = null;

    public TreeNode lcaDeepestLeaves(TreeNode root) {
        dfs(root, 0);
        return ans;
    }

    private int dfs(TreeNode node, int depth) {
        maxDepth = Math.max(maxDepth, depth);
        if (node == null) return depth;
        int left = dfs(node.left, depth + 1);
        int right = dfs(node.right, depth + 1);
        if (left == right && left == maxDepth) ans = node;
        return Math.max(left, right);
    }
}

class Solution {
public:
    TreeNode* lcaDeepestLeaves(TreeNode* root) {
        return dfs(root).second;
    }
private:
    pair<int, TreeNode*> dfs(TreeNode* node) {
        if (!node) return {0, nullptr};
        auto [ld, ll] = dfs(node->left);
        auto [rd, rl] = dfs(node->right);
        if (ld == rd) return {ld + 1, node};
        return ld > rd ? make_pair(ld + 1, ll) : make_pair(rd + 1, rl);
    }
};

Explanation

We need the lowest node that still sits above all of the deepest leaves. The neat insight is that a single bottom-up DFS can compute both the depth and the answer at the same time.

Each call returns a pair: (depth of the deepest leaf below me, the LCA of those deepest leaves). We combine the left and right results to decide what the current node should report.

If the left and right subtrees reach the same depth (ld == rd), then the deepest leaves are spread across both sides, so the current node itself is their meeting point — return (ld + 1, node). If one side goes deeper, the deepest leaves are entirely on that side, so we just carry up that side's LCA and add one to its depth.

Example: in [3,5,1,6,2,0,8,null,null,7,4] the deepest leaves are 7 and 4. At node 2 its left and right depths tie, so 2 becomes the LCA and that result bubbles up unchanged to the root.

Because every node is visited once, this is a clean single-pass O(n) solution.

Time: O(n) Space: O(h)