1123. Lowest Common Ancestor of Deepest Leaves - Leetcode Solution

Code Implementation

# 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

class Solution:
    def lcaDeepestLeaves(self, root: TreeNode) -> TreeNode:
        # Helper returns (LCA, depth)
        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)
            elif right_depth > left_depth:
                return (right_lca, right_depth + 1)
            else:
                return (node, left_depth + 1)
        lca, _ = dfs(root)
        return lca

// Definition for a binary tree node.
// struct TreeNode {
//     int val;
//     TreeNode *left;
//     TreeNode *right;
//     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
// };

class Solution {
public:
    pair dfs(TreeNode* node) {
        if (!node) return {nullptr, 0};
        auto left = dfs(node->left);
        auto right = dfs(node->right);
        if (left.second > right.second)
            return {left.first, left.second + 1};
        else if (right.second > left.second)
            return {right.first, right.second + 1};
        else
            return {node, left.second + 1};
    }
    TreeNode* lcaDeepestLeaves(TreeNode* root) {
        return dfs(root).first;
    }
};

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    private class Result {
        TreeNode node;
        int depth;
        Result(TreeNode n, int d) { node = n; depth = d; }
    }
    private Result dfs(TreeNode node) {
        if (node == null) return new Result(null, 0);
        Result left = dfs(node.left);
        Result right = dfs(node.right);
        if (left.depth > right.depth)
            return new Result(left.node, left.depth + 1);
        else if (right.depth > left.depth)
            return new Result(right.node, right.depth + 1);
        else
            return new Result(node, left.depth + 1);
    }
    public TreeNode lcaDeepestLeaves(TreeNode root) {
        return dfs(root).node;
    }
}

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {TreeNode}
 */
var lcaDeepestLeaves = function(root) {
    function dfs(node) {
        if (!node) return [null, 0];
        const [leftLCA, leftDepth] = dfs(node.left);
        const [rightLCA, rightDepth] = dfs(node.right);
        if (leftDepth > rightDepth) return [leftLCA, leftDepth + 1];
        if (rightDepth > leftDepth) return [rightLCA, rightDepth + 1];
        return [node, leftDepth + 1];
    }
    return dfs(root)[0];
};

Problem Description

Given the root of a binary tree, find the lowest common ancestor (LCA) of its deepest leaves.
The deepest leaves are defined as the nodes that are at the maximum depth in the tree. The lowest common ancestor is the lowest node in the tree that has all the deepest leaves as descendants (where we allow a node to be a descendant of itself).
Constraints:

There is exactly one valid solution for every input.
No node values are reused in the tree.
Input is given as the root node root of the binary tree.

Thought Process

To solve this problem, we first need to understand what the "deepest leaves" are and how to find their lowest common ancestor. A brute-force way would be:

Traverse the tree to find all the deepest leaves.
For each pair of deepest leaves, find their LCA, and then find the LCA of all these LCAs.

However, this approach is inefficient because finding LCA for every pair can be expensive.
We realize that we can combine the search for deepest leaves and their LCA in a single traversal. If we know for every subtree:

The depth of its deepest leaf
The LCA of the deepest leaves in that subtree

Then, we can use this information to compute the answer efficiently.
This leads us to a bottom-up recursive approach where, for each node, we ask:

What is the maximum depth among my left and right subtrees?
If both sides have the same maximum depth, then this node is the LCA of deepest leaves in its subtree.
If one side is deeper, then the LCA is the same as the LCA from that side.

Solution Approach

We use a recursive depth-first search (DFS) to traverse the tree. The key idea is to return, for each node:

The LCA of the deepest leaves in its subtree
The depth of the deepest leaf in its subtree

Step-by-step algorithm:

If the current node is null, return (null, 0) (no LCA, depth 0).
Recursively compute the result for the left child: (leftLCA, leftDepth).
Recursively compute the result for the right child: (rightLCA, rightDepth).
Compare leftDepth and rightDepth:
- If leftDepth > rightDepth: the deepest leaves are in the left subtree. Return (leftLCA, leftDepth + 1).
- If rightDepth > leftDepth: the deepest leaves are in the right subtree. Return (rightLCA, rightDepth + 1).
- If leftDepth == rightDepth: deepest leaves are equally deep in both subtrees. Current node is their LCA. Return (node, leftDepth + 1).
Start this process from the root. The LCA returned is the answer.

This approach is efficient because each node is visited once, and all information is passed up the tree without redundant computation.

Example Walkthrough

Let's use this example tree:

The deepest leaf is node 7 at depth 3 (root is depth 0).
All other leaves (6, 0, 8) are at depth 2 or less.
So, the LCA of the deepest leaf is the node itself (7), but since we want the LCA of all deepest leaves, and there's only one, the answer is 7.

Let's see a case with two deepest leaves:

Deepest leaves: 4 and 5 at depth 2.
LCA of 4 and 5 is node 1 (the root).

How does the algorithm work?

At node 4: returns (4, 1)
At node 5: returns (5, 1)
At node 2: left child depth 1, right child null, so returns (4, 2)
At node 3: right child depth 1, left child null, so returns (5, 2)
At root 1: left and right depths are both 2, so returns (1, 3)

Thus, the answer is node 1.

Time and Space Complexity

Brute-force approach:

Finding all deepest leaves: O(N)
Finding LCA for each pair: O(N^2) (since each LCA computation can be O(N) and there can be O(N) leaves)
Total: O(N^2)

Optimized approach (used here):

Each node is visited once in DFS: O(N)
At each node, constant work is done: O(1)
Space complexity is O(H), where H is the height of the tree, due to the recursion stack.
Total: O(N) time, O(H) space

This is optimal since every node must be inspected at least once.

Summary

The problem asks for the lowest common ancestor of the deepest leaves in a binary tree. By using a bottom-up recursive approach, we can compute both the depth and the LCA in a single traversal. This avoids redundant work and makes the solution both elegant and efficient. The key insight is to pass up both the depth and the candidate LCA at each step, so we always know, for each subtree, what the answer would be if the deepest leaves were all contained in that subtree. This method achieves O(N) time and O(H) space complexity, making it well-suited for large trees.

AlgoMap.io

Want Help Cracking FAANG?