CareerCup

node *ancestor(node *start,node *m,node *n)
node *left,*right;
if(start==NULL)
return NULL;
if((start->left==m||start->left==n||start->right==m||start->right==n)){
printf("Entered\n");
return start;
}
else{

left=ancestor(start->left,m,n);
right=ancestor(start->right,m,n);
if(left!=NULL&&right!=NULL)
return start;
else { printf("NAGA\n");
return (left!=NULL?left:right);
}
}

}

Node * findAncestor(Node * root,Node * node1, Node* node2)
{
if(root== NULL)
return NULL;
else if(node1->data == root->left->data && node2->data == root->right->data)
return root;
else if(node1->data< root->data && node2->data < root->data)
return findAncestor(root->left,Node * node1, Node* node2);
else if(node1->data > root->data && node2->data > root->data)
return findAncestor(root->right,Node * node1, Node* node2);
}

Sorry..Had put Node * node1 etc on the recursive call..

Node * findAncestor(Node * root,Node * node1, Node* node2)
{
if(root== NULL)
return NULL;
else if(node1->data == root->left->data && node2->data == root->right->data)
return root;
else if(node1->data< root->data && node2->data < root->data)
return findAncestor(root->left, node1, node2);
else if(node1->data > root->data && node2->data > root->data)
return findAncestor(root->right, node1, node2);
}

Hi Haripriya

I think this code doesnt work for all cases.
Suppose my tree is like 6
4 8
3 5
1
now i have to find least common ancestor for 1 5.Ur code will return NULL(ANS is 4),and problem is for a tree bt not for a binary search tree.Can u clarify if i made any mistake !!!!!!!!

note that the question is for binary tree not a binary search tree

There is no no need for a recursive solution. Also, that should be a clarifying question, but I'm 100% sure the interviewer means a BST.

public class TreeNode<T> where T : IComparable<T>{
     T Value {get; set;}
     TreeNode<T> Left {get; set;}
     TreeNode<T> Right {get; set;}
}

static TreeNode LowestCommonAncestor(TreeNode<T> Root, TreeNode<T> A, TreeNode<T> B)
{
     if(Root == null || A == null || B == null)
            throw new ArgumentNullException();
     TreeNode<T> current = Root;
     while(current != null){
          int ADirection = A.Value.CompareTo(current.Value);
          int BDirection = B.Value.CompareTo(current.Value);
          if(ADirection == 0 || BDirection == 0 || ADirection != BDirection){
               return current;
          }
          else{
               if(Adirection < 0){
                    current = current.Left;
               }
               else{
                    current = current.Right;
               }          
          }
     }
     return null
}

I dnt understand wth is going on. The solution is so very simple. You just need find the node where the given two nodes split up in the left and right direction. Here is the pseudo code:

void traverse(node *root, int A, int B)
{
    if(root == NULL)
         return;
    if(root->data > A && root->data > B)
         traverse(root->left);
    if(root->data < A && root->data < B)
         traverse(root->right);
    return root;
}

this is an SDET questions, its supposed to be easy. The question is incomplete. The exact same question is there in 'Programming interviews exposed' for a BST.

I think the solution proposed till now only looking for immedeate child node
i.e.
   root
   /   \
node1  node2

But it wont looking for the scenario like:
   root
   /   \
node1 temp-node1
      /    \
    node2  temp-node2
In this scenario node1 & node2 are not the immedeate children of root.
But root is their lowest common ancestor.


Below is a solution that take care of all the scenarios:

struct Node;
// Temporary container, for tracking both node.
struct container
{
   Node *node1;
   Node *node2;
} ctnr;
Node * findAncestor(Node * root,Node * node1, Node* node2)
{
  Node * left = 0;
  Node * right = 0;
  // root should not be null.
	assert(root != 0);
  // If its the node1, then store it in container
	if(root == node1)
	  ctnr.node1 = node1;
	// If its the node2, then store it in container  
	else if(root == node2)
	  ctnr.node2 = node2;
	// Traverse left subtree  
  if(root->left)
    left =  findAncestor(root->left,node1,node2);
  // Traverse right subtree  
  if(root->right)
    right =  findAncestor(root->right,node1,node2);
  // If both already found in left subtree, then returning their immedeate ancestor node.
  if(left != 0)  
  	return left;
  // If both already found in right subtree, then returning their immedeate ancestor node.	
  if(right != 0)  
  	return right;
  // Checking the marker in the container for both node's existance.
  // If they found then return the root node.
  if(ctnr.node1 != 0 && ctnr.node2 != 0)	
    return root;
  // Default return is 0.  
  return 0;  
}

bool LeastCommonAnscester(node *root, node *left, node *right, node **parent)
{
	node *ans = *parent;
	if(null == root)
	{
		return false;
	}

	bool found = false;
	if(root == left || root == right)
	{
		found = true;
	}
	
	bool leftFound = LeastCommonAnscenter(root->left, left, right, &parent);
	if(null != parent)
	{
		return true;
	}
	bool rightFound = LeastCommonAnscester(root->right, left, right, &parent);
	if(null != parent)
	{
		return true;
	}
	if((leftFound && rightFound) || (leftFound || rightFound) && found))
	{
		ans = root;
		return true;
	}
	else(((leftFound || rightFound) && !found) || ((!leftFound && !rightFound) && found)))
	{
		
		return true;
	}

	return false;

}

typedef struct tree_node* tree_ptr;
struct tree_node
{
int k;
tree_ptr left;
tree_ptr right;
};

int search(tree_ptr node,int x)
{
if(node->data == x)
{
return 1;
}
return search(node->left,x);
return search(node->right,x);
}

tree_ptr commonanc(tree_ptr root,tree_ptr m, tree_ptr n)
{
if(root)
{
if(m->left == n || m->right == n)
return m;
if(n->left == m || n->right == m)
return n;
int n_l = search(root->left,n->k);
int n_r = search(root->right,n->k);
int m_l = search(root->left,m->k);
int m_r = search(root->right,m->k);
if((n_l && m_r)||(m_l&&n_r))
return root;
else if( n_l&&m_l)
return commonanc(root->left,n,m);
else
return commonnc(root->right,n,m);

}
return NULL;
}

here is my solution , any comments are welcomed

public static Node FindLowestCommonAncestor(Node root,Node n1,Node n2)
        {
            if (root == null)
                return null;
            Node n = FindLowestCommonAncestor(root.Left, n1,n2);
            if (n==null)
               n= FindLowestCommonAncestor(root.Right, n1,n2);
           if (n != null)
               return n;
            else if (n==null && FindNode(root, n1) && FindNode(root, n2))
                return root;
            else
                return null;
        }
        static bool FindNode(Node root, Node n)
        {
            if(root==null)
                return false;
            if (root.Value == n.Value)
                return true;
            else if (FindNode(root.Left, n))
                return true;
            else if (FindNode(root.Right, n))
                return true;
            return false;
        }

the basic idea is nested post order search algorithm

As per Hari posted on 15th Jan the interviewer told that u r provided upward pointer to the parent and u r not given left and right child so I think we can approach like we find the intersection of two linked list.

h