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

The lowest common ancestor is defined between two nodes p and q as the lowest node in the tree that has both p and q as descendants (where we allow a node to be a descendant of itself).

Function Signature:

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

def lowest_common_ancestor(root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:
    """
    Find the lowest common ancestor of two nodes in a binary tree.

    Parameters:
    - root: The root of the binary tree.
    - p: The first node.
    - q: The second node.

    Returns:
    - TreeNode: The lowest common ancestor node.
    """
    # Your code here

Example:

# Example Binary Tree:
#        3
#       / \
#      5   1
#     / \ / \
#    6  2 0  8
#      / \
#     7   4

root = TreeNode(3,
                TreeNode(5, 
                         TreeNode(6), 
                         TreeNode(2, 
                                  TreeNode(7), 
                                  TreeNode(4)
                                  )
                         ),
                TreeNode(1, 
                         TreeNode(0), 
                         TreeNode(8)
                         )
                )

result1 = lowest_common_ancestor(root, root.left, root.right)  
print(result1.val)
assert result1.val == 3
# Explanation: LCA of nodes 5 and 1 is node 3

result2 = lowest_common_ancestor(root, root.left, root.left.right.right)  
assert result2.val == 5
print(result2.val)
# Explanation: LCA of nodes 5 and 4 is node 5

result3 = lowest_common_ancestor(root, root.left, root.right.left)  
assert result3.val == 3
print(result3.val)
# Explanation: LCA of nodes 5 and 0 is node 3

Note:

  • The given binary tree is not necessarily a binary search tree.
  • All node values are unique.
  • The given nodes p and q are guaranteed to be in the tree.
  • The data structure above allows you to traverse downwards only (from a parent to its children)

Instructions:

  • Write the lowest_common_ancestor function to solve the problem.
  • Implement your solution in Python.
  • Provide clear comments in your code.
  • Discuss the time and space complexity of your solution.

As always, we’ll share our solution to this problem tomorrow. Stay tuned 😊