The problem goes like this(pretty simple 1 line problem):- Given a Binary Tree (not necessarily Binary 'Search' Tree), its root and pointers to any 2 nodes of the tree, find out the first common ancestor of the Tree. A Node of the tree contains:

*data,*

*left subtree pointer*,

*right subtree pointer*but no

*'Parent pointer'.*

**Logic:**Let 'A' and 'B' be the given too node whose common ancestor we have to find. Now perform an inorder traversal of the tree and at every node call the

**'search(A)'**function on the

*left subtree*and

**search(B)**function on the

*right subtree.*When both the results are true, you can be assured that this current node is only the first common ancestor of A, and B,

**Reason:**Let the first common ancestor node be '

**C**'. Then below C on either of its subtree tree (left and right) one and only one of the nodes amongst A and B will be present and above the hierarchy of node C, both A and B will exist on just the 1 side.

Heres d pseudo code:

function getFirstCommonAncestor(root, A, B):

if root == NULL:

return NULL // the tree doesnt exists

// if the left subtree contains node A and the right subtree contains node B then we have found the first common ancestor

if(searchTree(root.left, A) and searchTree(root.right, B)):

return root

//else recursively find the common ancestor on its left and right subtrees and return if found

L = getFirstCommonAncestor(root.left, A, B)

R = getFirstCommonAncestor(root.right, A, B)

if L != None:

return L

if R != None:

return R

return None

Well, the algorithm is not so efficient but solves our purpose partially. I am yet to further include additional conditional checks and optimize the algorithm, but for most of the cases it works just fine. :)

Here goes the complete implementation in Python.

Note: Some of the extra checks are missing. You will figure that out yourself.

Bye for now.

Happy Coding !

Well,happy to see the python implementation!! Excellent Post!!Imagine u and Larry or Sergey go about finding your common ancestors using this algorithm on your respective family trees you would end up getting a 'Pan Troglodytes' as your common ancestor

ReplyDeleteP.S:For those not interested in biology use Google!!

/**

ReplyDelete* Find the first common ancestor of two given nodes in a binay search tree.

*

* @param args

* @author Pramod Chandoria

*/

public static Node lowestCommonParent(Node parent, Node node, int a, int b) {

if (node == null) {

return null;

}

if (a == node.data || b == node.data) {

return parent;

} else if (a < node.data && b > node.data) {

return node;

} else if (a < node.data){

return lowestCommonParent(node, node.left,a, b);

} else {

return lowestCommonParent(node, node.right,a, b);

}

}

IS VERY GOOD..............................

ReplyDeletenice posting.. thanks for sharing.

ReplyDelete