Lowest Common Ancestor of a Binary Tree

Clarify the problem:

• The problem requires us to find the lowest common ancestor (LCA) of two nodes in a binary tree.
• We need to implement a function that takes in the root of the binary tree and two nodes as input and returns their lowest common ancestor.
• The lowest common ancestor is defined as the lowest node in the tree that has both the given nodes as descendants.
• We need to consider the case where one node is a descendant of the other.

Analyze the problem:

• Input: Root of the binary tree, two nodes.
• Output: Lowest common ancestor of the two nodes.
• Constraints:
  • The number of nodes in the binary tree is between 2 and 10^5.
  • All node values are unique.
  • The given nodes are guaranteed to be present in the binary tree.

Design an algorithm:

• We can solve this problem using a recursive approach.
• We start traversing the binary tree from the root.
• If the current node is equal to either of the given nodes, we return that node as the LCA.
• Otherwise, we recursively search for the nodes in the left and right subtrees.
• If both nodes are found in different subtrees, the current node is the LCA.
• If only one node is found, we return that node as the LCA.
• If neither node is found, we return None as the LCA.

Explain your approach:

• We will implement a recursive algorithm to find the lowest common ancestor of the two nodes in a binary tree.
• We start by checking if the current node is equal to either of the given nodes.
• If it is, we return that node as the LCA.
• Otherwise, we recursively search for the nodes in the left and right subtrees.
• If both nodes are found in different subtrees, the current node is the LCA.
• If only one node is found, we return that node as the LCA.
• If neither node is found, we return None as the LCA.

Write clean and readable code:

python

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, p, q):
        if root is None or root == p or root == q:
            return root

        left_lca = self.lowestCommonAncestor(root.left, p, q)
        right_lca = self.lowestCommonAncestor(root.right, p, q)

        if left_lca and right_lca:
            return root
        if left_lca:
            return left_lca
        if right_lca:
            return right_lca

        return None

Test your code:

python

# Create the binary tree
root = TreeNode(3)
root.left = TreeNode(5)
root.right = TreeNode(1)
root.left.left = TreeNode(6)
root.left.right = TreeNode(2)
root.left.right.left = TreeNode(7)
root.left.right.right = TreeNode(4)
root.right.left = TreeNode(0)
root.right.right = TreeNode(8)

solution = Solution()
lca = solution.lowestCommonAncestor(root, root.left, root.right)
print(lca.val)  # Output: 3

lca = solution.lowestCommonAncestor(root, root.left, root.left.right.right)
print(lca.val)  # Output: 5

lca = solution.lowestCommonAncestor(root, root.left.left, root.left.right.right)
print(lca.val)  # Output: 5

Optimize if necessary:

• The provided solution has a time complexity of O(n), where n is the number of nodes in the binary tree.
• The space complexity is O(n) due to the recursive function calls in the worst case.
• This solution is efficient and optimal for the given problem.

Handle error cases:

• The code assumes that the input for the lowestCommonAncestor function is valid.
• If the root is None or either of the given nodes is None, the function will return None.

Discuss complexity analysis:

• The time complexity of the solution is O(n), where n is the number of nodes in the binary tree.
• The space complexity is O(n) due to the recursive function calls in the worst case.
• The solution is efficient and provides the correct output for the given problem.