Leetcode 1123. Lowest Common Ancestor of Deepest Leaves

1123. Lowest Common Ancestor of Deepest Leaves

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.

Approach 1:


class Solution {
    public TreeNode lcaDeepestLeaves(TreeNode root) {
        if (root == null)
            return null;
        int lh = height(root.left);
        int rh = height(root.right);
        if (rh == lh)
            return root;
        else if (lh > rh)
            return lcaDeepestLeaves(root.left);
        else
            return lcaDeepestLeaves(root.right);

    }

    private int height(TreeNode root) {
        if (root == null)
            return 0;
        int lh = 1 + height(root.left);
        int rh = 1 + height(root.right);
        return lh > rh ? lh : rh;
    }
}

Time Complexity: O(n) and Space Complexity: O(n)

Introduction

The "Lowest Common Ancestor of Deepest Leaves" problem is a tree-based algorithmic challenge that requires you to find the lowest common ancestor (LCA) of the deepest leaves in a binary tree. The LCA of two nodes in a tree is defined as the lowest node that is an ancestor of both nodes. This problem specifically focuses on the leaves of the tree, which are the nodes at the deepest level of the tree.

The objective is to find the LCA of all the nodes that are at the deepest level of the binary tree.

Problem Statement

Given a binary tree, return the lowest common ancestor (LCA) of the deepest leaves. The deepest leaves are the nodes that are at the maximum depth of the tree.

A binary tree node is represented as:

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

The problem requires finding the node that is the LCA of all nodes at the deepest level of the tree.

Approach

The solution to the "Lowest Common Ancestor of Deepest Leaves" problem involves a combination of depth-first search (DFS) and tree traversal techniques. The general approach is:

Find the deepest leaves: Traverse the tree to determine the deepest level and collect all the leaf nodes at that level.
Find the LCA: Once we have the deepest leaves, we need to find their lowest common ancestor. This can be achieved by recursively finding the LCA of their ancestors.
Use DFS for tree traversal: A DFS traversal helps in both determining the depth of the tree and identifying the LCA. By recursively visiting each node and passing back the deepest node(s), we can find the desired LCA.

Algorithm

The algorithm to solve this problem can be broken down into the following steps:

Start DFS traversal: Begin at the root and recursively traverse all nodes in the tree.
Track maximum depth: As you traverse, keep track of the maximum depth and the corresponding nodes at that level.
Return the LCA: Once the deepest level is reached, return the common ancestor of the deepest leaves.
Post-order traversal: Ensure that you perform a post-order traversal (left-right-root) so that you process the children nodes first and then their parents.

Example

Let's consider an example to better understand the solution:

        Tree:
                 3
               /   \
              5     1
            /   \   /  \
           6     2 0    8
                / \
               7   4

In this case, the deepest leaves are 7, 4, and 8. The LCA of these nodes is 2, as it is the lowest node that is an ancestor to all of them.

Code Implementation

Below is a Python implementation of the algorithm that finds the lowest common ancestor of the deepest leaves:

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

def lcaDeepestLeaves(root):
    def dfs(node):
        if not node:
            return (0, None)  # (depth, ancestor)

        left_depth, left_lca = dfs(node.left)
        right_depth, right_lca = dfs(node.right)

        # If left and right depths are the same, this node is the LCA
        if left_depth == right_depth:
            return (left_depth + 1, node)

        # Otherwise, return the deeper side
        if left_depth > right_depth:
            return (left_depth + 1, left_lca)
        else:
            return (right_depth + 1, right_lca)

    depth, ancestor = dfs(root)
    return ancestor

In this code: - We perform a DFS traversal of the tree starting from the root. - At each node, we recursively find the depth of its left and right subtrees. - If the depths are equal, the current node is the LCA of the deepest leaves. - If one side is deeper, we return the deeper side's LCA. - The function returns the LCA of the deepest leaves once the DFS traversal is complete.

Time Complexity

The time complexity of this algorithm is O(n), where n is the number of nodes in the binary tree. This is because we visit each node exactly once during the DFS traversal.

The space complexity is O(h), where h is the height of the tree. This is due to the recursive call stack during the DFS traversal, which can go as deep as the height of the tree.

Conclusion

The "Lowest Common Ancestor of Deepest Leaves" problem is a great way to practice tree traversal and understanding the concept of the lowest common ancestor (LCA). By using DFS traversal and tracking the deepest leaves, we can efficiently find the LCA of the deepest nodes. This problem also helps in understanding recursion and the importance of post-order traversal in tree-related problems.