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.

 

.

.

C

A

P

T

A

I

N

I

N

T

E

R

V

I

E

W

.

.

Solution:

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

 

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

w

Connecting to %s