Lowest Common Ancestor of Deepest Leaves

#1646 Most AskedMedium

Lowest Common Ancestor of Deepest Leaves #1646 Most Asked

Medium

Google

8 views

Topics:

TreesRecursion

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/

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Can the tree be empty? What should I return in that case?
What is the range of values for the node data in the binary tree? Are the values unique?
If there are multiple deepest leaves, and their lowest common ancestor is the root, should I return the root node itself, or is there a specific way to represent that case?
By 'deepest leaves', do you mean leaves that are at the maximum depth from the root? Or is there another definition I should consider?
Is the provided tree guaranteed to be a valid binary tree, or do I need to handle cases with cycles or invalid parent-child relationships?

Brute Force Solution

Approach

The brute force method for finding the lowest common ancestor of the deepest leaves involves first finding all the deepest leaves in the tree. Then, for every possible pair of these leaves, we'll find their lowest common ancestor and compare the depth of that ancestor to determine the overall lowest common ancestor.

Here's how the algorithm would work step-by-step:

First, we need to figure out how deep the tree goes to find the deepest level.
Next, we walk through the entire tree and find all the leaves that are at the deepest level. These are our deepest leaves.
Now, we take two of these deepest leaves at a time and find their common ancestor. To do this, we can climb upwards from each leaf towards the root, keeping track of the path we take.
Find the point where the paths from each leaf meet. This point is their lowest common ancestor.
We then note down the depth (how far away from the root) of that lowest common ancestor.
Repeat the process of finding the lowest common ancestor for every possible pair of deepest leaves.
Compare all the lowest common ancestors we found. The ancestor that is deepest (farthest from the root) or equivalently, the lowest, is the lowest common ancestor of the deepest leaves and our final answer.

Code Implementation

def lowest_common_ancestor_of_deepest_leaves_brute_force(root):
    def find_depth(node, current_depth):
        if not node:
            return current_depth
        return max(find_depth(node.left, current_depth + 1),\
                   find_depth(node.right, current_depth + 1))

    def find_deepest_leaves(node, current_depth, deepest_level, deepest_leaves):
        if not node:
            return

        if not node.left and not node.right:
            if current_depth == deepest_level:
                deepest_leaves.append(node)
            return

        find_deepest_leaves(node.left, current_depth + 1, deepest_level, deepest_leaves)
        find_deepest_leaves(node.right, current_depth + 1, deepest_level, deepest_leaves)

    def find_path_to_root(node, target, path):
        if not node:
            return False

        path.append(node)

        if node == target:
            return True

        if find_path_to_root(node.left, target, path) or find_path_to_root(node.right, target, path):
            return True

        path.pop()
        return False

    # Determine the depth of the deepest leaves.
    deepest_level = find_depth(root, 0)

    deepest_leaves = []
    find_deepest_leaves(root, 0, deepest_level, deepest_leaves)

    lowest_common_ancestor = None
    lowest_common_ancestor_depth = -1

    # Iterate through all pairs of deepest leaves.
    for i in range(len(deepest_leaves)):
        for j in range(i + 1, len(deepest_leaves)):
            first_leaf = deepest_leaves[i]
            second_leaf = deepest_leaves[j]

            first_path = []
            second_path = []

            find_path_to_root(root, first_leaf, first_path)
            find_path_to_root(root, second_leaf, second_path)

            current_lowest_common_ancestor = None
            current_lowest_common_ancestor_depth = -1

            # Find the lowest common ancestor for the pair.
            for k in range(min(len(first_path), len(second_path))):
                if first_path[len(first_path) - 1 - k] == second_path[len(second_path) - 1 - k]:
                    current_lowest_common_ancestor = first_path[len(first_path) - 1 - k]
                    current_lowest_common_ancestor_depth = len(first_path) - 1 - k
                else:
                    break

            # Update LCA if a deeper LCA is found.
            if current_lowest_common_ancestor_depth > lowest_common_ancestor_depth:
                lowest_common_ancestor = current_lowest_common_ancestor
                lowest_common_ancestor_depth = current_lowest_common_ancestor_depth

    # Handles the single node/leaf cases
    if not lowest_common_ancestor and deepest_leaves:
        return deepest_leaves[0]

    # Account for when the root is the LCA
    if not lowest_common_ancestor:
        return root

    return lowest_common_ancestor

Big(O) Analysis

Time Complexity

O(n^3) – Finding the maximum depth of the tree takes O(n) time, where n is the number of nodes. Identifying the deepest leaves also requires traversing the tree, which is another O(n) operation. Finding the lowest common ancestor for each pair of deepest leaves involves tracing paths up the tree, potentially up to the root, which can take O(n) time in the worst case. Since we iterate through all possible pairs of the deepest leaves, and in the worst case, the number of deepest leaves could be proportional to n, the pairing and LCA calculation contributes O(n^2 * n) = O(n^3). Therefore, the overall time complexity is dominated by the pairwise LCA calculations, resulting in O(n^3).

Space Complexity

O(N) – The space complexity is dominated by two factors: the recursion depth during the tree traversal to find the deepest level and deepest leaves, and the storage of paths from each deepest leaf to the root. The recursion depth can reach N in a skewed tree, where N is the number of nodes. Furthermore, storing the paths from the deepest leaves to the root also requires, in the worst case, storing a path of length N for each leaf. Combining these, the auxiliary space is proportional to the depth of the tree (N) due to the call stack and storing paths, resulting in O(N) space complexity.

Optimal Solution

Approach

The best way to find the lowest common ancestor of the deepest leaves is to explore the tree and keep track of depth as you go. The clever part is to simultaneously figure out the deepest level and which node is the ancestor, all in one pass.

Here's how the algorithm would work step-by-step:

Start by exploring the tree, going down each branch until you reach a leaf.
As you explore, keep track of the current depth, and if you find a leaf at a depth greater than any depth previously seen, then you have a new deepest level. The current node is the new candidate for the lowest common ancestor.
If you find a leaf at the same depth as the deepest level, it means you've found another deepest leaf. This means the current node might be the lowest common ancestor, or one of its ancestors could be.
To handle the case of multiple deepest leaves, when you find a node with deepest leaves in both its left and right subtrees, this node is the lowest common ancestor of those leaves. In this situation, this node should be recorded as the lowest common ancestor.
Continue exploring the tree. After visiting every node, the node you have marked as the lowest common ancestor of the deepest leaves will be the correct result.

Code Implementation

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def lowest_common_ancestor_of_deepest_leaves(root):
    deepest_level = 0
    lowest_common_ancestor = None

    def depth_first_search(node, current_depth):
        nonlocal deepest_level, lowest_common_ancestor

        if not node:
            return current_depth - 1

        left_depth = depth_first_search(node.left, current_depth + 1)
        right_depth = depth_first_search(node.right, current_depth + 1)

        # Update the deepest level and LCA if a new deepest level is found
        if left_depth == right_depth and left_depth >= deepest_level:
            deepest_level = left_depth
            lowest_common_ancestor = node

        # When a new deepest level is detected.
        elif left_depth > right_depth:
            return left_depth
        else:
            return right_depth

    depth_first_search(root, 0)

    # After depth first search, we have the LCA.
    return lowest_common_ancestor

Big(O) Analysis

Time Complexity

O(n) – The algorithm performs a single Depth-First Search (DFS) traversal of the binary tree. Each node in the tree is visited exactly once. At each node, a constant amount of work is done to update the deepest level and the lowest common ancestor candidate. Therefore, the time complexity is directly proportional to the number of nodes in the tree, which we represent as 'n'.

Space Complexity

O(H) – The space complexity is determined by the maximum depth of the recursion stack during the tree traversal, where H is the height of the tree. In the worst-case scenario, if the tree is skewed (like a linked list), the height can be equal to N, where N is the number of nodes. The recursive calls add stack frames up to a maximum depth of H, leading to O(H) space complexity. The algorithm also uses a few variables to keep track of the deepest level and the lowest common ancestor candidate, but their space usage is constant and doesn't depend on the input size, so it is dominated by the recursion depth. Thus, the overall auxiliary space complexity is O(H).

Edge Cases

Case	How to Handle
Null or empty tree	Return null immediately as there are no nodes, and hence no LCA.
Single node tree	Return the single node as it is both the deepest leaf and its own ancestor.
Skewed tree (left or right leaning)	The algorithm should correctly identify the deepest leaf at the end of the skew and return it as the LCA.
Tree with all nodes at the same depth	The root of the tree is the lowest common ancestor of all the leaves and should be returned.
Very large tree (potential stack overflow with recursion)	Consider using iterative approach (e.g., level order traversal) to avoid stack overflow issues with very deep trees.
Tree with duplicate values (value not unique)	Node values are not used for LCA identification; only tree structure is considered.
Deepest leaves are siblings	The parent of the deepest leaves is the correct LCA, and the algorithm should correctly traverse up to it.
Multiple sets of deepest leaves at the same depth	The algorithm should correctly identify and return the lowest common ancestor of all deepest leaves, even if they are in disconnected subtrees.

Null or empty tree

How to Handle:

Return null immediately as there are no nodes, and hence no LCA.

Single node tree

How to Handle:

Return the single node as it is both the deepest leaf and its own ancestor.

Skewed tree (left or right leaning)

How to Handle:

The algorithm should correctly identify the deepest leaf at the end of the skew and return it as the LCA.

Tree with all nodes at the same depth

How to Handle:

The root of the tree is the lowest common ancestor of all the leaves and should be returned.

Very large tree (potential stack overflow with recursion)

How to Handle:

Consider using iterative approach (e.g., level order traversal) to avoid stack overflow issues with very deep trees.

Tree with duplicate values (value not unique)

How to Handle:

Node values are not used for LCA identification; only tree structure is considered.

Deepest leaves are siblings

How to Handle:

The parent of the deepest leaves is the correct LCA, and the algorithm should correctly traverse up to it.

Multiple sets of deepest leaves at the same depth

How to Handle:

The algorithm should correctly identify and return the lowest common ancestor of *all* deepest leaves, even if they are in disconnected subtrees.