algoadvance

You are given a binary tree and two nodes p and q. Your task is to find the lowest common ancestor (LCA) of these two nodes in the tree.

The definition of the lowest common ancestor is as follows:

Here’s the function signature you need to implement:

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

def lowestCommonAncestor(root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:
    pass

Clarifying Questions

  1. What should we return if one or both of the nodes p or q are not present in the tree?
    • Assume that p and q will always exist in the tree.
  2. Can the binary tree contain duplicate values?
    • No, all the values in the binary tree are unique.
  3. Is the binary tree a binary search tree (BST)?
    • No, assume it’s a regular binary tree, not necessarily a BST.

Strategy

To find the LCA of two nodes in a binary tree, a recursive approach is quite effective. Here’s the plan:

  1. Base Case: If the current node is None, return None. If the current node is either p or q, return the current node.
  2. Recursive Case: Recurse on the left and right subtrees.
  3. Post-processing:
    • After recursion, if both left and right recursion calls return non-None values, it means p and q are found in different subtrees of the current node. Therefore, the current node is their LCA.
    • If only one of the left or right returns a non-None value, return that non-None value because that indicates that both p and q are found in the subtree rooted at that returned node.

Code

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

def lowestCommonAncestor(root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:
    # Base case
    if root is None or root == p or root == q:
        return root

    # Search in left and right subtree
    left = lowestCommonAncestor(root.left, p, q)
    right = lowestCommonAncestor(root.right, p, q)
    
    # If both left and right are non-null, the current node is the LCA
    if left and right:
        return root
    
    # Otherwise, return the non-null subtree
    return left if left is not None else right

Time Complexity

The time complexity of this solution is O(N) where N is the number of nodes in the binary tree. This is because in the worst case, we need to visit all the nodes to find p and q.

The space complexity is O(H), where H is the height of the tree, due to the recursive call stack. In the worst case of a skewed tree, this can be up to O(N). For a balanced tree, this would be O(log N).

Try our interview co-pilot at AlgoAdvance.com