1123. Lowest-Common-Ancestor-Of-Deepest-Leaves

Classic graph problem, initial thoughts are to use BFS or DFS to find the deepest leaf nodes of the graph.

After looking at hints (hints are there for a reason!!!!!), I ‘realized’ that we can do a post-order traversal of the tree using recursion and keep track of the current lowest common ancestor node.

We can check the depth of the left and right subtrees of the current node. We have three cases:

• if the left subtree is deeper than the right subtree:
  • we can return the depth of the left subtree + 1 and the left node (since the left node is the lowest common ancestor of deepest nodes)
• if the right subtree is deeper than the left subtree:
  • we can return the depth of the right subtree + 1 and the right node (since the right node is the lowest common ancestor of deepest nodes)
• if the left and right subtrees are equal:
  • that means that the current node is the lowest common ancestor of the deepest nodes, so we can return the depth of either subtree + 1 and the current node.

At the leaf nodes, we can return 0 and None since there are no left or right subtrees.

We can then return the result of the post-order traversal and we are done :D

class Solution(object):
    def lcaDeepestLeaves(self, root):
        """
        :type root: Optional[TreeNode]
        :rtype: Optional[TreeNode]
        """
        def traverse(node):
            if node is None:
                return 0, None

            left_depth, left = traverse(node.left)
            right_depth, right = traverse(node.right)
            
            if left_depth > right_depth:
                return left_depth + 1, left
            if right_depth > left_depth:
                return right_depth + 1, right
            
            return left_depth + 1, node

        res = traverse(root)[1]

        return res

Time Complexity: O(n)

Space Complexity: O(n)

Time Taken: forgot to keep track