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.