235. Lowest Common Ancestor of a Binary Search Tree
Given a binary search tree (BST), find the lowest common ancestor (LCA) of two given nodes in the BST.
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 = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8 Output: 6 Explanation: The LCA of nodes 2 and 8 is 6.
Example 2:
Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4 Output: 2 Explanation: The LCA of nodes 2 and 4 is 2, since a node can be a descendant of itself according to the LCA definition.
Example 3:
Input: root = [2,1], p = 2, q = 1 Output: 2
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 BST.
Source
Code
In [1]:
def lowest_common_ancestor(root, p, q):
"""Build path for each value (using stacks) and compare them."""
def path(root, target):
stack = [root]
curr = root
while curr and curr != target:
curr = curr.right if curr.val < target.val else curr.left
stack.append(curr)
return stack
if not root:
return None
path_p = path(root, p)
path_q = path(root, q)
i = 0
while i < min(len(path_p), len(path_q)) and path_p[i] == path_q[i]: # mind the order
i += 1
return path_p[i-1]
In [2]:
def lowest_common_ancestor(root, p, q):
"""Recursive approach."""
if p.val <= root.val <= q.val or p.val >= root.val >= q.val:
return root
if p.val < root.val and q.val < root.val:
return lowest_common_ancestor(root.left, p, q)
else:
return lowest_common_ancestor(root.right, p, q)
Follow up:
Solve it both recursively and iteratively.
Code
In [8]:
def lowest_common_ancestor(root, p, q):
"""Iterative approach."""
while True:
if p.val <= root.val <= q.val or p.val >= root.val >= q.val:
return root
if p.val < root.val and q.val < root.val:
root = root.left
else:
root = root.right