Problem Description
Given two nodes, p and q, in a binary tree where each node has a pointer to its parent, return their lowest common ancestor (LCA). The LCA is defined as the lowest node that has both p and q as descendants (a node can be a descendant of itself).
Key Insights
- Each node has a parent pointer, so you can traverse from any node to the root.
- By determining the depth of each node, you can “align” the two nodes to the same depth.
- When both nodes are aligned, traverse upward simultaneously until they meet.
- This approach guarantees finding the LCA with O(h) time complexity, where h is the height of the tree.
Space and Time Complexity
Time Complexity: O(h), where h is the height of the tree. Space Complexity: O(1)
Solution
We first compute the depth of both nodes by moving up their parent pointers. If one node is deeper, move it upward until both nodes are at the same level. Then, move both nodes upward one step at a time until they meet; the meeting point is the lowest common ancestor. This approach uses constant extra space and leverages the parent pointer for an efficient solution.