1123. Lowest Common Ancestor of Deepest Leaves | Solution

Q: Is Lowest Common Ancestor of Deepest Leaves easy or hard?

Lowest Common Ancestor of Deepest Leaves is rated Medium difficulty. The challenge is recognizing that the deepest leaves determine the ancestor based on subtree depth comparison. Once you frame the problem as a DFS returning depth and node together, the implementation becomes straightforward.

Q: Lowest Common Ancestor of Deepest Leaves Python/Java solution

Python and Java implementations usually follow the same DFS pattern: recursively compute left and right subtree depths, then return the node that represents the LCA when both depths match. The logic fits naturally with recursive functions in Python and helper methods in Java classes.

Q: How to solve Lowest Common Ancestor of Deepest Leaves in O(n)?

Perform a post-order DFS where each recursive call returns the maximum depth and the LCA candidate for that subtree. Compare the left and right subtree depths. If they are equal, return the current node as the LCA; otherwise return the deeper subtree's candidate. Since every node is processed once, the complexity is O(n).

Q: What is the best approach for Lowest Common Ancestor of Deepest Leaves?

The most efficient approach uses a single Depth-First Search traversal that returns both the deepest depth and the corresponding LCA node from each subtree. If the left and right subtree depths are equal, the current node becomes the LCA. This method runs in O(n) time and O(h) space where h is the height of the tree.

Q: Is Lowest Common Ancestor of Deepest Leaves asked at Google/Amazon/Meta?

Tree and LCA variations frequently appear in interviews at companies like Google, Amazon, and Meta. This problem tests understanding of binary tree traversal, depth tracking, and combining subtree results, which are common interview themes.

Q: What data structure is used in Lowest Common Ancestor of Deepest Leaves?

The primary data structure is a binary tree. The solution typically uses Depth-First Search recursion or Breadth-First Search with a queue. Some implementations also maintain parent pointers or hash maps when computing the LCA of multiple nodes.

Q: What is the time complexity of Lowest Common Ancestor of Deepest Leaves?

The optimal solution runs in O(n) time because each node in the binary tree is visited exactly once during traversal. Recursive DFS uses O(h) space for the call stack, while a BFS-based solution may require O(n) space for the queue and parent tracking.

The problem

Given the root of a binary tree, return the lowest common ancestor of its deepest leaves.

Recall that:

The node of a binary tree is a leaf if and only if it has no children
The depth of the root of the tree is 0. if the depth of a node is d, the depth of each of its children is d + 1.
The lowest common ancestor of a set S of nodes, is the node A with the largest depth such that every node in S is in the subtree with root A.

Example 1:

Input: root = [3,5,1,6,2,0,8,null,null,7,4]
Output: [2,7,4]
Explanation: We return the node with value 2, colored in yellow in the diagram.
The nodes coloured in blue are the deepest leaf-nodes of the tree.
Note that nodes 6, 0, and 8 are also leaf nodes, but the depth of them is 2, but the depth of nodes 7 and 4 is 3.

Example 2:

Input: root = [1]
Output: [1]
Explanation: The root is the deepest node in the tree, and it's the lca of itself.

Example 3:

Input: root = [0,1,3,null,2]
Output: [2]
Explanation: The deepest leaf node in the tree is 2, the lca of one node is itself.

Constraints:

The number of nodes in the tree will be in the range [1, 1000].
0 <= Node.val <= 1000
The values of the nodes in the tree are unique.

Note: This question is the same as 865: https://leetcode.com/problems/smallest-subtree-with-all-the-deepest-nodes/

Approach overview

Problem Overview: Given a binary tree, return the lowest common ancestor (LCA) of all the deepest leaf nodes. The deepest leaves are the nodes located at the maximum depth in the tree. If multiple deepest leaves exist in different subtrees, the answer is the lowest node that is an ancestor of all of them.

Approach 1: Recursive Deepest Leaves and LCA (DFS) (Time: O(n), Space: O(h))

This approach performs a single post-order traversal using Depth-First Search. For every node, compute the depth of its left and right subtrees. If both sides reach the same maximum depth, the current node becomes the lowest common ancestor of the deepest leaves in those subtrees. If one subtree is deeper, propagate the deeper subtree's candidate node upward. Each recursive call returns a pair: the deepest depth found and the corresponding LCA node. Because every node is visited exactly once, the time complexity is O(n). The recursion stack uses O(h) space where h is the tree height. This solution is concise and naturally fits problems involving Tree recursion.

Approach 2: Iterative Deepest Leaves and LCA using BFS (Time: O(n), Space: O(n))

This method first finds all deepest nodes using level-order traversal with Breadth-First Search. Iterate through the tree level by level and track the nodes in the last processed level, which represent the deepest leaves. After collecting these nodes, compute their lowest common ancestor by walking upward using parent references or by repeatedly merging pairs of nodes using an LCA routine on the Binary Tree. BFS guarantees that the final processed level contains exactly the deepest nodes. The traversal visits each node once for O(n) time and stores nodes in a queue with O(n) auxiliary space.

Recommended for interviews: The recursive DFS approach is usually preferred. It solves the problem in a single traversal and directly combines depth computation with LCA discovery. Interviewers expect you to recognize that the deepest leaves determine the LCA based on subtree depths. The BFS approach demonstrates a clear understanding of level traversal and is useful when you explicitly need to identify the deepest level first, but it typically requires extra bookkeeping.

Approach 1: Recursive Deepest Leaves and LCA

This approach involves recursively finding the depth of the subtree at each node and returning the LCA of the deepest leaves.

The main idea is to perform a post-order traversal to determine the depth of left and right subtrees. If the depths are equal, the current node is the LCA. If the left subtree is deeper, recursively find the LCA in the left subtree, and similarly for the right subtree.

Python

class Solution:
    def lcaDeepestLeaves(self, root: 'TreeNode') -> 'TreeNode':
        def dfs(node):
            if not node:
                return (0, None)
            left_depth, left_lca = dfs(node.left)
            right_depth, right_lca = dfs(node.right)
            if left_depth > right_depth:
                return (left_depth + 1, left_lca)
            elif right_depth > left_depth:
                return (right_depth + 1, right_lca)
            else:
                return (left_depth + 1, node)
        return dfs(root)[1]

Java

class Solution {
    public TreeNode lcaDeepestLeaves(TreeNode root) {
        return dfs(root).getValue();
    }

    private Pair<Integer, TreeNode> dfs(TreeNode node) {
        if (node == null) return new Pair<>(0, null);
        Pair<Integer, TreeNode> left = dfs(node.left), right = dfs(node.right);
        if (left.getKey() == right.getKey())
            return new Pair<>(left.getKey() + 1, node);
        else if (left.getKey() > right.getKey())
            return new Pair<>(left.getKey() + 1, left.getValue());
        else
            return new Pair<>(right.getKey() + 1, right.getValue());
    }
}

C++

#include <iostream>
using namespace std;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution {
public:
    TreeNode* lcaDeepestLeaves(TreeNode* root) {
        return dfs(root).second;
    }

private:
    pair<int, TreeNode*> dfs(TreeNode* node) {
        if (!node) return {0, NULL};
        auto left = dfs(node->left);
        auto right = dfs(node->right);
        int d1 = left.first, d2 = right.first;
        return {max(d1, d2) + 1, d1 == d2 ? node : (d1 > d2 ? left.second : right.second)};
    }
};

JavaScript

class TreeNode {
    constructor(val) {
        this.val = val;
        this.left = this.right = null;
    }
}

function lcaDeepestLeaves(root) {
    const dfs = (node) => {
        if (!node) return [0, null];
        const [leftDepth, leftLCA] = dfs(node.left);
        const [rightDepth, rightLCA] = dfs(node.right);
        if (leftDepth > rightDepth) return [leftDepth + 1, leftLCA];
        if (rightDepth > leftDepth) return [rightDepth + 1, rightLCA];
        return [leftDepth + 1, node];
    };
    return dfs(root)[1];
}

#include <stdio.h>
#include <stdlib.h>

struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
};

// Helper function to calculate the depth of the tree and find LCA
int dfs(struct TreeNode* root, int *maxDepth, struct TreeNode **lca, int depth) {
    if (!root) return depth - 1;
    int left = dfs(root->left, maxDepth, lca, depth + 1);
    int right = dfs(root->right, maxDepth, lca, depth + 1);
    int currDepth = left > right ? left : right;
    if (left == right && currDepth >= *maxDepth) {
        *maxDepth = currDepth;
        *lca = root;
    }
    return currDepth;
}

struct TreeNode* lcaDeepestLeaves(struct TreeNode* root) {
    int maxDepth = 0;
    struct TreeNode *lca = NULL;
    dfs(root, &maxDepth, &lca, 0);
    return lca;
}

using System;

public class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int x) { val = x; }
}

public class Solution {
    public TreeNode LcaDeepestLeaves(TreeNode root) {
        return Dfs(root).Item2;
    }

    private (int, TreeNode) Dfs(TreeNode node) {
        if (node == null) return (0, null);
        var left = Dfs(node.left);
        var right = Dfs(node.right);
        if (left.Item1 > right.Item1) return (left.Item1 + 1, left.Item2);
        if (right.Item1 > left.Item1) return (right.Item1 + 1, right.Item2);
        return (left.Item1 + 1, node);
    }
}

This Python solution defines a recursive helper `dfs` that returns a tuple containing the maximum depth found and the associated LCA within the subtree rooted at the current node. If both child depths are the same, it means the current node is the LCA for the deepest nodes below it.

Complexity

Time Complexity: O(N)

Space Complexity: O(H)

Try this approach in the editor

Approach 2: Iterative Deepest Leaves and LCA using BFS

Instead of recursive DFS, another approach is to use Breadth-First Search (BFS) to traverse levels of the tree iteratively, keeping track of the nodes at the deepest level. This level-based traversal ensures we gather all deepest leaves in a set. Finally, we use a standard method to determine LCA from this set of nodes.

Python

from collections import deque

class Solution:
    def lcaDeepestLeaves(self, root):
        if not root:
            return None
        q = deque([root])
        while q:
            size = len(q)
            deepest = list(q)
            for _ in range(size):
                node = q.popleft()
                if node.left:
                    q.append(node.left)
                if node.right:
                    q.append(node.right)
        return self.findLCA(root, set(deepest))

    def findLCA(self, node, nodes):
        if not node:
            return None
        if node in nodes:
            return node
        left = self.findLCA(node.left, nodes)
        right = self.findLCA(node.right, nodes)
        if left and right:
            return node
        return left if left else right

Java

import java.util.*;

class Solution {
    public TreeNode lcaDeepestLeaves(TreeNode root) {
        if (root == null) return null;
        Queue<TreeNode> queue = new LinkedList<>();
        Set<TreeNode> deepest = new HashSet<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            int size = queue.size();
            deepest.clear();
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                deepest.add(node);
                if (node.left != null) queue.add(node.left);
                if (node.right != null) queue.add(node.right);
            }
        }
        return lowestCommonAncestor(root, deepest);
    }
    
    private TreeNode lowestCommonAncestor(TreeNode node, Set<TreeNode> nodes) {
        if (node == null) return null;
        if (nodes.contains(node)) return node;
        TreeNode left = lowestCommonAncestor(node.left, nodes);
        TreeNode right = lowestCommonAncestor(node.right, nodes);
        if (left != null && right != null) return node;
        return left != null ? left : right;
    }
}

C++

#include <queue>
#include <unordered_set>
using namespace std;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution {
public:
    TreeNode* lcaDeepestLeaves(TreeNode* root) {
        if (!root) return nullptr;
        queue<TreeNode*> q;
        unordered_set<TreeNode*> deepest;
        q.push(root);
        while (!q.empty()) {
            int sz = q.size();
            deepest.clear();
            for (int i = 0; i < sz; ++i) {
                TreeNode* node = q.front(); q.pop();
                deepest.insert(node);
                if (node->left) q.push(node->left);
                if (node->right) q.push(node->right);
            }
        }
        auto it = deepest.begin();
        if (deepest.size() == 1) return *it;
        while (true) {
            while (root && deepest.find(root) == deepest.end()) {
                if (it == deepest.end()) it = deepest.begin();
                root = *it;
                ++it;
            }
            if (root) return root;
        }
    }
};

JavaScript

function lcaDeepestLeaves(root) {
    if (!root) return null;
    let queue = [root];
    let lastLevel = []; 

    while (queue.length) {
        let size = queue.length;
        lastLevel = [...queue];
        for (let i = 0; i < size; i++) {
            let node = queue.shift();
            if (node.left) queue.push(node.left);
            if (node.right) queue.push(node.right);
        }
    }

    function findLCA(node, nodeSet) {
      if (!node) return null;
      if (nodeSet.has(node)) return node;
      let left = findLCA(node.left, nodeSet);
      let right = findLCA(node.right, nodeSet);
      if (left && right) return node;
      return left || right;
    }

    const nodeSet = new Set(lastLevel);
    return findLCA(root, nodeSet);
}

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

#define MAX_QUEUE_SIZE 1000

struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
};

struct TreeNode* queue[MAX_QUEUE_SIZE];
int front = -1, rear = -1;

bool isQueueEmpty() {
    return front == -1 || front > rear;
}

void enqueue(struct TreeNode* node) {
    if(rear == MAX_QUEUE_SIZE - 1) return;
    if(front == -1) front = 0;
    queue[++rear] = node;
}

struct TreeNode* dequeue() {
    if(isQueueEmpty()) return NULL;
    return queue[front++];
}

struct TreeNode* lcaDeepestLeaves(struct TreeNode* root) {
    if (!root) return NULL;
    
    while (true) {
        front = rear = -1;
        enqueue(root);
        int levelSize = rear - front + 1;
        while (!isQueueEmpty()) {
            for (int i = 0; i < levelSize; ++i) {
                struct TreeNode* node = dequeue();
                if (node->left) enqueue(node->left);
                if (node->right) enqueue(node->right);
            }
            levelSize = rear - front + 1;
            if (levelSize == 0) {
                return root;
            }
            root = queue[front];
        }
    }
}

using System;
using System.Collections.Generic;

public class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int x) { val = x; }
}

public class Solution {
    public TreeNode LcaDeepestLeaves(TreeNode root) {
        if (root == null) return null;
        Queue<TreeNode> queue = new Queue<TreeNode>();
        queue.Enqueue(root);
        TreeNode last = null;
        while (queue.Count > 0) {
            int size = queue.Count;
            for (int i = 0; i < size; i++) {
                last = queue.Dequeue();
                if (last.left != null) queue.Enqueue(last.left);
                if (last.right != null) queue.Enqueue(last.right);
            }
        }
        return Lca(root, new HashSet<TreeNode>(queue));
    }

    private TreeNode Lca(TreeNode node, HashSet<TreeNode> nodes) {
        if (node == null) return null;
        if (nodes.Contains(node)) return node;
        TreeNode left = Lca(node.left, nodes);
        TreeNode right = Lca(node.right, nodes);
        if (left != null && right != null) return node;
        return left ?? right;
    }
}

The Python implementation uses a queue for level-by-level traversal. Once the deepest nodes are recognized, `findLCA` helps track the node whose subtree encompasses all deepest nodes, returning the LCA as soon as it's brought back through recursion.

Complexity

Time Complexity: O(N)

Space Complexity: O(N)

Try this approach in the editor

Approach 3: DFS

We design a function dfs(root) that returns a tuple (l, d), where l is the deepest common ancestor of node root, and d is the depth of node root. The execution logic of the function dfs(root) is as follows:

If root is null, return the tuple (None, 0);
Otherwise, we recursively call dfs(root.left) and dfs(root.right), obtaining tuples (l, d1) and (r, d2). If d1 > d2, the deepest common ancestor of root is l, and the depth is d1 + 1; if d1 < d2, the deepest common ancestor of root is r, and the depth is d2 + 1; if d1 = d2, the deepest common ancestor of root is root, and the depth is d1 + 1.

In the main function, we call dfs(root) and return the first element of its return value to get the deepest common ancestor node.

The time complexity is O(n), and the space complexity is O(n). Here, n is the number of nodes in the binary tree.

TypeScript

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */

function lcaDeepestLeaves(root: TreeNode | null): TreeNode | null {
    const dfs = (root: TreeNode | null): [TreeNode | null, number] => {
        if (root === null) {
            return [null, 0];
        }
        const [l, d1] = dfs(root.left);
        const [r, d2] = dfs(root.right);
        if (d1 > d2) {
            return [l, d1 + 1];
        }
        if (d1 < d2) {
            return [r, d2 + 1];
        }
        return [root, d1 + 1];
    };
    return dfs(root)[0];
}

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
type pair struct {
	first  *TreeNode
	second int
}

func lcaDeepestLeaves(root *TreeNode) *TreeNode {
	var dfs func(root *TreeNode) pair
	dfs = func(root *TreeNode) pair {
		if root == nil {
			return pair{nil, 0}
		}
		l, r := dfs(root.Left), dfs(root.Right)
		d1, d2 := l.second, r.second
		if d1 > d2 {
			return pair{l.first, d1 + 1}
		}
		if d1 < d2 {
			return pair{r.first, d2 + 1}
		}
		return pair{root, d1 + 1}
	}
	return dfs(root).first
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Recursive Deepest Leaves and LCA	Time Complexity: O(N) Space Complexity: O(H)
Iterative Deepest Leaves and LCA using BFS	Time Complexity: O(N) Space Complexity: O(N)
DFS	–

Approach

Complexity

Recursive Deepest Leaves and LCA

Time Complexity: O(N)

Space Complexity: O(H)

Iterative Deepest Leaves and LCA using BFS

Time Complexity: O(N)

Space Complexity: O(N)

DFS

–

Complexity analysis

Approach	Time	Space	When to Use
Recursive Deepest Leaves + LCA (DFS)	O(n)	O(h)	Best general solution. Single traversal and minimal extra memory.
Iterative Deepest Leaves + LCA using BFS	O(n)	O(n)	Useful when explicitly identifying the deepest level first or when avoiding recursion.

Frequently asked questions

Is Lowest Common Ancestor of Deepest Leaves easy or hard?

Lowest Common Ancestor of Deepest Leaves is rated Medium difficulty. The challenge is recognizing that the deepest leaves determine the ancestor based on subtree depth comparison. Once you frame the problem as a DFS returning depth and node together, the implementation becomes straightforward.

Lowest Common Ancestor of Deepest Leaves Python/Java solution

Python and Java implementations usually follow the same DFS pattern: recursively compute left and right subtree depths, then return the node that represents the LCA when both depths match. The logic fits naturally with recursive functions in Python and helper methods in Java classes.

How to solve Lowest Common Ancestor of Deepest Leaves in O(n)?

Perform a post-order DFS where each recursive call returns the maximum depth and the LCA candidate for that subtree. Compare the left and right subtree depths. If they are equal, return the current node as the LCA; otherwise return the deeper subtree's candidate. Since every node is processed once, the complexity is O(n).

What is the best approach for Lowest Common Ancestor of Deepest Leaves?

The most efficient approach uses a single Depth-First Search traversal that returns both the deepest depth and the corresponding LCA node from each subtree. If the left and right subtree depths are equal, the current node becomes the LCA. This method runs in O(n) time and O(h) space where h is the height of the tree.

Is Lowest Common Ancestor of Deepest Leaves asked at Google/Amazon/Meta?

Tree and LCA variations frequently appear in interviews at companies like Google, Amazon, and Meta. This problem tests understanding of binary tree traversal, depth tracking, and combining subtree results, which are common interview themes.

What data structure is used in Lowest Common Ancestor of Deepest Leaves?

The primary data structure is a binary tree. The solution typically uses Depth-First Search recursion or Breadth-First Search with a queue. Some implementations also maintain parent pointers or hash maps when computing the LCA of multiple nodes.

What is the time complexity of Lowest Common Ancestor of Deepest Leaves?

The optimal solution runs in O(n) time because each node in the binary tree is visited exactly once during traversal. Recursive DFS uses O(h) space for the call stack, while a BFS-based solution may require O(n) space for the queue and parent tracking.

Lowest Common Ancestor of Deepest Leaves solution and explanation

The problem

Approach overview

Approach 1: Recursive Deepest Leaves and LCA

Approach 2: Iterative Deepest Leaves and LCA using BFS

Approach 3: DFS

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Lowest Common Ancestor of Deepest Leaves solution and explanation

The problem

Approach overview

Approach 1: Recursive Deepest Leaves and LCA

Approach 2: Iterative Deepest Leaves and LCA using BFS

Approach 3: DFS

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems