Question: How would you find the first common ancestor of two nodes in a binary search tree? First as in the lowest in the tree. Another way to ask is to find the lowest common ancestor of two nodes.
Challenge: Do you know the answer to this question? Post in the comments. Answers will be posted March 6th.
Meanwhile, check out the challenges from previous weeks here.
Answer:
TreeNode findFirstCommonAncestor(TreeNode root, TreeNode p,
TreeNode q) {
if (root == null) {
return null;
}
if (root == p || root == q) {
return root;
}
TreeNode left = findFirstCommonAncestor(root.left, p, q);
TreeNode right = findFirstCommonAncestor(root.right, p, q);
if ((left == p && right == q) ||
(left == q && right == q)) {
return root;
}
return (left != null) ? left : right;
}
Alternate:
TreeNode findFirstCommonAncestor(TreeNode root, int p, int q) {
if (root == null) {
return null;
}
if (root.value == p || root.value == q) {
return root;
}
if (root.value > p && root.value > q ) {
return findFirstCommonAncestor(root.left, p, q);
}
else if (root.value < p && root.value < q ) {
return findFirstCommonAncestor(root.right, p, q);
}
else {
return root;
}
}
Thanks Dave and Sunil for pointing out the alternate solution.
