Challenge – Find First Common Ancestor

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.

 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;
    }
}

Comments

Popular posts from this blog

AGRICULTURAL SCIENTIST RECRUITMENT BOARD

HSC Exam Time Table 2013 Arts, Commerce, Science

What are cookies and its types? Where are cookies used?