We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Lowest Common Ancestor of a Binary Tree

Difficulty: Medium

Problem Description

Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree. The lowest common ancestor is defined as the lowest node in the tree that has both nodes as descendants (where a node can be a descendant of itself).

Key Insights

  • The LCA is the deepest node that is an ancestor to both given nodes.
  • We can traverse the tree using Depth-First Search (DFS) to find the LCA.
  • If either of the nodes is found during traversal, we can return that node as a potential ancestor.
  • The search continues until both nodes are found, ensuring the lowest common ancestor is identified.

Space and Time Complexity

Time Complexity: O(N), where N is the number of nodes in the tree, as we may need to traverse all nodes in the worst case. Space Complexity: O(H), where H is the height of the tree, due to the recursive stack space used in DFS.

Solution

We will use a Depth-First Search (DFS) approach to traverse the binary tree. Starting from the root, we will check if the current node is either of the nodes we are looking for. If we find one of the nodes, we return that node. During the traversal, if we find both nodes among the left and right subtrees of a node, then that node is the lowest common ancestor.

Code Solutions

def lowestCommonAncestor(root, p, q):
    # Base case: if the current node is None, return None
    if not root:
        return None
    
    # If the current node is either p or q, return the current node
    if root == p or root == q:
        return root
    
    # Recursively search for LCA in the left and right subtrees
    left = lowestCommonAncestor(root.left, p, q)
    right = lowestCommonAncestor(root.right, p, q)
    
    # If both left and right calls returned non-null, this node is the LCA
    if left and right:
        return root
    
    # Return the non-null child if one of them is LCA
    return left if left else right
← Back to All Questions