Lowest Common Ancestor Of Deepest Leaves - Leetcode Solution

Problem Description:

Given a binary tree, find the lowest common ancestor (LCA) 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. We define the depth of the leaves as being 1. We define the depth of any other node depth of the parent + 1. The lowest common ancestor of a set of nodes is the node where all the nodes in the set descend.

Solution:

We can solve this problem using a recursive approach. We can start by finding the deepest leaves of the binary tree. Once we have found the deepest leaves, we can find their lowest common ancestor.

To find the deepest leaves, we can use a recursive helper function that returns the depth of a node. We can start from the root node and recursively compute the depth of its left and right children. We can then return the maximum depth of both the left and right children. If the depth of the left and right children are the same and are equal to the maximum depth, it means that the current node is a deepest leaf. We can add this to a list of deepest leaves.

After we have found the deepest leaves, we can find their lowest common ancestor. We can do this by recursively finding the lowest common ancestor of the left and right children of the current node. If the current node is a deepest leaf, we can return the current node as it is the lowest common ancestor of the deepest leaves.

The code implementation is as follows:

Python Code:

class TreeNode:     def init(self, x):         self.val = x         self.left = None         self.right = None

class Solution:     def lcaDeepestLeaves(self, root: TreeNode) -> TreeNode:                 def depth(node: TreeNode) -> int:             if not node:                 return 0             return max(depth(node.left), depth(node.right)) + 1                     def dfs(node: TreeNode) -> Tuple[TreeNode, int]:             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 node, left_depth + 1             elif left_depth > right_depth:                 return left_lca, left_depth + 1             else:                 return right_lca, right_depth + 1                                          return dfs(root)[0]

The time complexity of this solution is O(N) as we visit each node of the binary tree only once. The space complexity of this solution is O(H) where H is the height of the binary tree. This is because we are using a recursive approach. The maximum call stack size will be equal to the height of the binary tree.

1