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 !