Lowest Common Ancestor Of A Binary Tree Ii - Leetcode Solution

Problem Statement:

Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.

The LCA for a binary tree is defined as the the lowest node that has both node p and node q as descendants (where we allow a node to be a descendant of itself). The LCA of a node itself is often defined to be itself.

Example: Consider the following binary tree:

     3
    / \
   5   1
  / \   \
 6   2   8
    / \
   7   4

Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1 Output: 3 Explanation: The LCA of nodes 5 and 1 is 3.

Solution:

We can solve this problem with the help of Depth First Search (DFS) algorithm. As we move down the tree from the root node, at each node we check if the current node is equal to either of the given two nodes, p and q. If the current node is equal to either of the nodes, then we mark it as seen and return it. Otherwise, we continue exploring the left and right children of the current node recursively.

If we have found either p or q in both the left and right subtrees, then that means the current node is the LCA. If we have found only one of the nodes in either the left or the right subtree, then we return that node since it is still possible that the other node exists in the other subtree. If we have not found either of the nodes in either of the subtrees, then we return null indicating that neither of the nodes exists in this subtree.

In order to keep track of the ancestors of the nodes we can pass a set of nodes in the function argument and if we find the node p or q then we add it into the set. This will be useful if we have to return to the parent node after exploring the child nodes to check if both nodes (p and q) are in the parent node’s subtree.

Code:

Here’s the Python implementation of the above solution:

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

class Solution: def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:

    # base case: if the root is null or either of the nodes is the root then return the root
    if not root or root == p or root == q:
        return root
    
    # recursively explore the left and right subtrees
    left_subtree = self.lowestCommonAncestor(root.left, p, q)
    right_subtree = self.lowestCommonAncestor(root.right, p, q)
    
    # if we have found both nodes in either the left or right subtree
    if left_subtree and right_subtree:
        return root
    
    # if we have found only one of the nodes in either the left or right subtree
    if not left_subtree:
        return right_subtree
    if not right_subtree:
        return left_subtree

Time Complexity:

The time complexity of the above solution is O(n) where n is the number of nodes in the binary tree. This is because we are visiting every node in the tree once.

Space Complexity:

The space complexity of the above solution is O(h) where h is the height of the binary tree. This is because the maximum number of function calls on the call stack would be equal to the height of the tree.

1