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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Lowest Common Ancestor of a Binary Tree

Number: 236

Difficulty: Medium

Paid? No

Companies: Meta, Amazon, Google, Microsoft, LinkedIn, TikTok, Apple, Oracle, Bloomberg, Intuit, Adobe, Atlassian, Yandex, Salesforce, Yahoo, GE Healthcare, PayPal, Flipkart, Wayfair, Wix

Problem Description

Given a binary tree, find the lowest common ancestor (LCA) of two given nodes p and q. The LCA is defined as the lowest node in the tree that has both p and q as descendants (a node can be a descendant of itself). The tree consists of unique values and both p and q exist within the tree.

Key Insights

  • Use a depth-first search (DFS) traversal to explore the tree.
  • If the current node is either p or q, it could be the LCA.
  • Recursively find p and q in the left and right subtrees.
  • If both left and right recursive calls return a non-null value, then the current node is the LCA.
  • If only one side returns a non-null value, propagate that value up the recursion.

Space and Time Complexity

Time Complexity: O(n), where n is the number of nodes in the tree since each node is visited once. Space Complexity: O(h), where h is the height of the tree due to the recursion stack (O(n) in the worst case of a skewed tree).

Solution

We solve the problem using recursion with depth-first search. The algorithm checks if the current node matches p or q. It then recursively searches the left and right subtrees. If both subtrees contain one of p or q, the current node is the LCA. Otherwise, the algorithm forwards the non-null result up the recursion. This approach naturally handles cases where one node is an ancestor of the other.

Code Solutions

# Definition for a binary tree node.
# 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 current node is None, return None.
        if root is None:
            return None
        
        # If the current node is either p or q, return the current node.
        if root == p or root == q:
            return root
        
        # Search for p and q in the left and right subtrees.
        left = self.lowestCommonAncestor(root.left, p, q)
        right = self.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 node.
        return left if left is not None else right
← Back to All Questions