Lowest Common Ancestor of a Binary Tree
Problem Description
Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.
According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”
Example 1:
Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
Output: 3
Example 2:
Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
Output: 5
Example 3:
Input: root = [1,2], p = 1, q = 2
Output: 1
Constraints:
- The number of nodes in the tree is in the range [2, 105].
- -109 <= Node.val <= 109
- All
Node.valare unique. p != qpandqwill exist in the tree.
Solve it on LeetCode
Approaches
1. Recursive Traversal with Multiple Returns
Intuition:
This approach involves recursively traversing the binary tree from the root node and returning the lowest common ancestor. The idea is to essentially perform a post-order traversal of the tree while returning conditions that help conclude the LCA.
- If the current node is one of the target nodes
porq, we return this node as a candidate for the LCA. - Recursively search both left and right subtrees for the target nodes
pandq. - If both left and right subtree calls return a non-null value, it means
pandqare found in different subtrees of the current node, making the current node the LCA. - If only one of the subtree calls returns a non-null value, this means both nodes are located in that subtree, and we return that value upward.
Code:
- Time Complexity: O(N), where N is the number of nodes in the binary tree. Each node is visited once.
- Space Complexity: O(N) - In the worst case, the space due to recursion stack will be N for a skewed tree.
2. Iterative using Parent Pointers
Intuition:
In this approach, we utilize a parent pointer for all nodes starting from the root. Once we have parent pointers, we can track the path from each node p and q to the root. The first common node in these two paths is the LCA.
- Use a hashmap to store the parent of each node.
- Traverse the tree to populate the parent pointers.
- Track back from node
pto the root and save all visited ancestors in a set. - Track back from node
qand find the first common ancestor in the set.
Code:
- Time Complexity: O(N), where N is the number of nodes in the binary tree. We traverse each node once to populate the parent pointers.
- Space Complexity: O(N) - The space required for the hashmap and visited set in the worst case.
3. Optimized Recursive Traversal
Intuition:
This approach is a refined version of the first recursive approach. It involves a single recursive post-order traversal to find the LCA more clearly and concisely.
- If the current node is
null, returnnull, indicating that neitherpnorqis found below. - If the current node is equal to
porq, return the current node. - Otherwise, recursively call on the left and right subtrees.
- If both left and right calls return non-null, the current node is the LCA.
- Otherwise, return the non-null value from left or right.
Code:
- Time Complexity: O(N), where N is the number of nodes in the binary tree. Each node is visited once.
- Space Complexity: O(N) - In the worst case, the space due to recursion stack will be N for a skewed tree.