Problem of The Day: Lowest Common Ancestor of a Binary Tree III
Problem Statement
Intuition
The problem asks to find the Lowest Common Ancestor (LCA) of two nodes in a binary tree where each node has a parent pointer. The idea is to trace the paths of the two nodes to the root and find where they diverge. The last common node in their paths is the LCA.
Approach
- We first check if one node is a descendant of the other using Depth First Search (DFS).
- If neither is a descendant of the other, we trace both nodes’ paths to the root using the parent pointers and compare the paths.
- The last common node between the two paths is the LCA.
Complexity
-
Time complexity: \(O(h)\), where \(h\) is the height of the tree. This is because we traverse from each node to the root, and the height of the tree determines the maximum number of steps.
-
Space complexity: \(O(h)\), as we store the path from each node to the root, which can be at most the height of the tree.
Code
"""
# Definition for a Node.
class Node:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
self.parent = None
"""
class Solution:
def dfs(self, root, target):
if not root:
return False
if root is target:
return True
return self.dfs(root.left, target) or self.dfs(root.right, target)
def helper(self, p, q):
parents1 = []
parents2 = []
while p.parent or q.parent:
if p.parent:
p = p.parent
parents1.append(p)
if q.parent:
q = q.parent
parents2.append(q)
parents1.reverse()
parents2.reverse()
prev = None
for i in range(min(len(parents1), len(parents2))):
if parents1[i] is not parents2[i]:
return prev
prev = parents1[i] if parents1[i] else parents2[i]
return prev
def lowestCommonAncestor(self, p: 'Node', q: 'Node') -> 'Node':
if self.dfs(p, q):
return p
if self.dfs(q, p):
return q
return self.helper(p, q)
