Lowest Common Ancestor of a Binary Tree
Given a binary tree, find the lowest common ancestor (LCA) of two given nodes 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).
Example
Consider the following binary tree:
Tree: 10 / \ 5 15 / \ \ 3 7 20 / \ / 1 8 17
- The lowest common ancestor of nodes 5 and 15 is node 10.
- The lowest common ancestor of nodes 3 and 7 is node 5.
Our solution for finding the Lowest Common Ancestor (LCA) of two nodes in a binary tree follows a recursive approach. At each node, we check if either of the two nodes (p or q) is the current node. If the current node matches one of the target nodes, we return the current node as a potential LCA.
Next, we recursively traverse the left and right subtrees of the current node. The recursion returns the LCA found in the left subtree and the LCA found in the right subtree.
- If both left and right recursive calls return non-null values, it means that one node (
porq) was found in the left subtree and the other was found in the right subtree. Therefore, the current node is the LCA ofpandq. - If only one of the left or right calls returns a non-null value, it means both nodes are in the same subtree, and the non-null return value is the LCA.
- If both left and right calls return null, we return null to indicate that neither
pnorqis found in this subtree.
This recursive process continues until the lowest node that has both p and q as descendants is found.
from typing import Optional
class TreeNode:
def __init__(self, val: int = 0, left: Optional['TreeNode'] = None, right: Optional['TreeNode'] = None):
self.val = val
self.left = left
self.right = right
def lowest_common_ancestor(root: Optional[TreeNode], p: TreeNode, q: TreeNode) -> Optional[TreeNode]:
if not root or root == p or root == q:
return root
left = lowest_common_ancestor(root.left, p, q)
right = lowest_common_ancestor(root.right, p, q)
if left and right:
return root
return left if left else rightTime Complexity: The time complexity of this solution is O(n), where n is the number of nodes in the tree. This is because in the worst case, the algorithm visits every node once.
Space Complexity: The space complexity is O(h), where h is the height of the tree. This space is used for the recursive call stack. In the worst case of a completely unbalanced tree, this could be O(n), while in a balanced tree, it would be O(log n).
