Lowest Common Ancestor of Deepest Leaves

Patrick Leaton
Published: Nov. 23, 2021, 9:40 p.m.
Problem Description

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/

 

The description was taken from https://leetcode.com/problems/lowest-common-ancestor-of-deepest-leaves/.

Problem Solution

#O(N) Time, O(N) Space
class Solution:
    def lcaDeepestLeaves(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        depths = {}
       
        def inorder(node:TreeNode, depth:int) -> None:
            if not node:
                return
            inorder(node.left, depth + 1)
            if depth in depths:
                depths[depth].add(node.val)
            else:
                depths[depth] = set([node.val])
            inorder(node.right, depth + 1)
       
        def postorder(node:TreeNode) -> TreeNode:
            if not node or node.val in depths[deepest]:
                return node
            left = postorder(node.left)
            right = postorder(node.right)
            if left and right:
                return node
            else:
                return left or right
       
        inorder(root, 0)
        deepest = max(depths.keys())
        return postorder(root)

Problem Explanation

This problem is very similar to Lowest Common Ancestor of a Binary Tree.

The main difference, however, is we aren't given two nodes that we are trying to find the LCA for.  

Here, the target nodes that are undetermined are the ones at the deepest level of the tree.  To find these nodes we can do a traversal through the tree to map each node with its depth.  After we do that, we can do a postorder traversal, similar to the first LCA problem, and only return the nodes that are within the deepest layer.

By doing this we will tackle two scenarios: there is only one leaf node at the deepest layer of the tree or there are multiple.

Let's start by initializing our depths dictionary.

        depths = {}

Next, we will create a helper function to map each node value to each depth.

        def inorder(node:TreeNode, depth:int) -> None:
            if not node:
                return

 

If the current node is null, we will return.

            if not node:
                return

 

Otherwise, we'll increment the depth by one for each additional child visit and we will place the node mapping to each depth within a set so that we can have constant lookup times for them within our next traversal.

            inorder(node.left, depth + 1)
            if depth in depths:
                depths[depth].add(node.val)
            else:
                depths[depth] = set([node.val])
            inorder(node.right, depth + 1)

Next, we will make our postorder helper function to find the LCA.

        def postorder(node:TreeNode) -> TreeNode:

 

If the current node is null or the current node is in the deepest layer of the tree, we will return the current node.

If the current node is null then this base case will return null.  Otherwise, we will be able to pass the current node up the tree which will be explained more momentarily.

            if not node or node.val in depths[deepest]:
                return node

 

If we haven't hit a base case then we will continue our Depth-First Search on the left and right children before processing the current node.

            left = postorder(node.left)
            right = postorder(node.right)

 

Okay, so here is the main logic of this problem.

If we have a scenario where there is only a single leaf node at the deepest layer of the tree, then when we hit the prior base case, we will pass that node up to the root where it will be returned when we call this function.

Otherwise, if we have a scenario where there are multiple, then the subtree root that has a node passed up from both its left and right child branches will be the LCA.  Remember, we are doing a postorder traversal here so each child node is being processed before its parent.

If the current node's left and right children have returned a node to it, then we will return the current node as it is the LCA.

            if left and right:
                return node

 

Otherwise, we will keep passing up the node that was passed to the current node from whichever child, if there was a node passed.

            else:
                return left or right

Now that we have our helper functions built, we just need to run the initial inorder function on the root, calculate the deepest layer and return the LCA by calling the postorder function on the root.

        inorder(root, 0)
        deepest = max(depths.keys())
        return postorder(root)