CareerCup

Which part of the word "iterative" is not clear ...........

do inoder traversal iteratively, and store the values in array A
say array A contains  values (5,9,u,6,11,v,22,10)
and u and v are the nodes for which we have to find LCA.
now only thing remains is to check for every node between u and v, 
(we can use devide and conquer in nodes between u and v)
the node from which we can reach both u and v is LCA.

public class LeastCommonAncestor {
    
    private int[] tree;
    
    public LeastCommonAncestor(int[] tree)
    {
        this.tree= new int[tree.length+1];
        System.arraycopy(tree,0, this.tree, 1, tree.length);
    }
    
    public int getLCA(int a, int b)
    {
        int apos=-1, bpos=-1;
        
        for(int i=0; (apos==-1||bpos==-1) && i<tree.length; i++)
        {
            apos= tree[i]==a?i:apos;
            bpos= tree[i]==b?i:bpos;
        }
        
        if(apos*bpos<0)
            return -1;
        
        while(apos!=bpos)
        {
            if(apos>bpos)
                apos/=2;
            else bpos/=2;
        }
        
        return apos;
    }
    
    public static void main(String args[]) throws FileNotFoundException, IOException            
    {
        BufferedReader br= new BufferedReader(new InputStreamReader( new FileInputStream(new File("C:\\LCA.txt"))));
        System.out.println("Enter tree");
        String[] treestring= br.readLine().split(" ");
        int[] tree= new int[treestring.length];
        
        for(int i=0; i<treestring.length; i++)
        {
            tree[i]= treestring[i].equals("NULL")?-1:Integer.parseInt(treestring[i]);
        }
        System.out.println("Enter A and B");
        int a= Integer.parseInt(br.readLine());
        int b= Integer.parseInt(br.readLine());
        
        LeastCommonAncestor lca= new LeastCommonAncestor(tree);
        int pos= lca.getLCA(a, b);

        System.out.println(lca.tree[pos]);
    }
}

LCA(node* root,p,q)
{
        //finding ancestors...
	vector<node*> a,b;
	while(p->parent)
	{
          a.push_back(p->parent);
	  p = p->parent;
     	}
        while(q->parent)
	{
          b.push_back(q->parent);
	  q = q->parent;
     	}
	vector<node*> &c,&d;
        if(a.size() > b.size())
	{
	  a.erase(a.size()-b.size());
	}
	else
	{
	  b.erase(b.size()-a.size());
	}
        
        //binary search for first equal elements...
        int u = 0;
        int v = a.size();
	while(u<v)
        {
	    int mid = (u+v)/2;
            if(a[mid] == b[mid])
            v = mid;
            else
            u = mid;
	}
        return a[u];
}

DFS

NodeType* findLCA(NodeType* root, NodeType* e1, NodeType* e2)
{
    if(root == NULL) return NULL;
    if(root == e1 || root == e2) return root;
    NodeType* lRet = findLCA(root->l, e1, e2);
    NodeType* rRet = findLCA(root->r, e1, e2);
    if(lRet && rRet) return root;
    if(!lRet) return rRet;
    return lRet;
}

Convert the tree into list where
left child->2n
right child->2n+i
while traversing and converting to a list, note the indexes of the list where the data of the nodes are saved say IndexX and IndexY.

then all you have to do is match IndexX/2 and IndexY/2 by using left shift operator.
and your job is done in O(n)
with an efficiency with worst case: n+log(n)

int LCA(struct treenode* root,int a,int b)
{
if(root==NULL)
return 0;

if(((root->data < a) && (root->data >b))|| ((root->data > a) && (root->data <b)) ||(root->data == a) || (root->data ==b))
return root->data;
if((root->data < a) && (root->data <b))
LCA(root->right,a,b);
if((root->data > a) && (root->data >b))
LCA(root->left,a,b);
}

public TreeNode LowestCommonAncestor(TreeNode a, TreeNode b){
while (a != b && (a != null) && (b != null)){
if (a.depth == b.depth){
a = a.parent;
b = b.parent;
}

if (a.depth > b.depth){
a = a.parent;
}else{
b = b.parent;
}
}

if ( a == b){
return a;
}
throw new RuntimeException(“Two input nodes aren’t in the same binary tree”);
}

Node* LCA_itr(Node *root, Node *n1, Node  *n2){
        while(root!=NULL){
                if(root->val==n1->val || root->val==n2->val){
                        return root;
                }
                if((root->val > n1->val && root->val < n2->val) || (root->val < n1->val && root->val > n2->val)){
                        return root;
                }
                if(root->val > n1 && root->val > n2->val){
                        root=root->left;
                }
                if(root->val < n1->val && root->val < n2->val){
                        root=root->right;
                }
        }
        return NULL;
}

Iteratively find pre-order and post-order and in-order sequence of the tree.
now, if u , v are the given tree nodes, LCA of u,v should occur :
1) between u, v in in-order sequence
2) before u, v in pre-order
3) after u, v in post order.
find the common node (unique) following all these rules. this will be the LCA.

Tnode *LCA(Tnode *a,Tnode *b)
{
Tnode *p=a;
while (p!=root)
{
p->flag=a->key;
p=p->father;
}
root->flag=a->key;

*p=b;
while (p->flag!=a->key) p=p->father;

return p;
}

void LCA_dfs(int u)
{
int tmp=++depth;
b[++bn]=tmp; f[tmp]=u; at[u]=bn;
for (int i=0; i<son[u].size(); i++)
{
int v=son[u][i];
LCA_dfs(v);
b[++bn]=tmp;
}
}

inline void RMQ_init(int n)
{
for (int i=1; i<=n; i++) d[i][0]=b[i];
int m=floor(log(n*1.0)/log(2.0));
for (int j=1; j<=m; j++)
for (int i=1; i<=n-(1<<j)+1; i++)
d[i][j]=min(d[i][j-1],d[i+(1<<(j-1))][j-1]);
}

inline int RMQ(int l,int r)
{
int k=floor((log(r-l+1)*1.0)/log(2.0));
return min(d[l][k],d[r-(1<<k)+1][k]);
}

inline int LCA(int a,int b)
{
if (at[a]>at[b]) swap(a,b);
return f[RMQ(at[a],at[b])];
}

What is the property of the binary tree? If it is like Binary Search Tree i.e. left < root < right, then just iteratively go up from node with lower key until encounter the first ancestor whose key is greater than the other node's key. If it is only normal tree, find the path from each node to the root, then go back and find the early common node of two paths.

If there is only pointers from parent to child nodes, we can use the property of Binary search tree to search from the root and choose to search the left or right subtree.

Here is my code, I implement two solutions:


import java.util.HashMap;
import java.util.LinkedList;
import java.util.Queue;

public class Problem_7_find_lowest_common_ancessstor {
// I implement two solutions, Solution1() and Solution2()

public static BinaryTreeNode return_first_common_ancesstor(
BinaryTreeNode head,BinaryTreeNode o1,BinaryTreeNode o2){
BinaryTreeNode parent=null;
parent=Solution1(head,o1,o2);
parent=Solution2(head,o1,o2);
return parent;
}

public static BinaryTreeNode Solution1(BinaryTreeNode head,BinaryTreeNode o1,BinaryTreeNode o2){

HashMap<BinaryTreeNode,BinaryTreeNode> parentmap=new HashMap<BinaryTreeNode,BinaryTreeNode>();
Solution1_createParentmap(head,parentmap);

HashMap<BinaryTreeNode,Boolean> o1parent=new HashMap<BinaryTreeNode,Boolean>();
o1parent.put(o1, true);
BinaryTreeNode currentParento1=parentmap.get(o1);
while(currentParento1!=null){
o1parent.put(currentParento1, true);
currentParento1=parentmap.get(currentParento1);
}
BinaryTreeNode currentParento2=o2;
while(currentParento2!=null){
if(o1parent.containsKey(currentParento2)){
return currentParento2;
}
currentParento2=parentmap.get(currentParento2);
}

return null;
}

public static void Solution1_createParentmap(BinaryTreeNode head,HashMap<BinaryTreeNode,BinaryTreeNode> parentmap){
if(head==null){
System.out.println("This tree is empty!");
return ;
}
Queue<BinaryTreeNode> nodeQueue=new LinkedList<BinaryTreeNode>();
nodeQueue.add(head);
parentmap.put(head, null);
while(!nodeQueue.isEmpty()){
BinaryTreeNode currentNode=nodeQueue.poll();
if(currentNode.leftchild!=null){
parentmap.put(currentNode.leftchild,currentNode);
nodeQueue.add(currentNode.leftchild);
}
if(currentNode.rightchild!=null){
parentmap.put(currentNode.rightchild,currentNode);
nodeQueue.add(currentNode.rightchild);
}
}
}



public static BinaryTreeNode Solution2(BinaryTreeNode head,BinaryTreeNode o1,BinaryTreeNode o2){
if((!Solution2_contains_node(head,o1))||(!Solution2_contains_node(head,o2))){
return null;
}
if(o1==o2){
return o1;
}
BinaryTreeNode current=head;
while(Solution2_contains_node(current,o1)&&Solution2_contains_node(current,o2)){

if(Solution2_contains_node(current.leftchild,o1)&&Solution2_contains_node(current.leftchild,o2)){
current=current.leftchild;
continue;
}
if(Solution2_contains_node(current.rightchild,o1)&&Solution2_contains_node(current.rightchild,o2)){
current=current.rightchild;
continue;
}
break;
}

return current;
}
public static boolean Solution2_contains_node(BinaryTreeNode head,BinaryTreeNode node){
if(head==null){
return false;
}
if(head==node){
return true;
}
boolean lefthas=Solution2_contains_node(head.leftchild,node);
boolean righthas=Solution2_contains_node(head.rightchild,node);
if((lefthas)||(righthas)){
return true;
}
else{
return false;
}
}

// main function for test
public static void main(String[] args) {
BinaryTreeNode head=new BinaryTreeNode(16);
head.insertleft(new BinaryTreeNode(12));
head.insertright(new BinaryTreeNode(18));
head.leftchild.insertleft(new BinaryTreeNode(6));
head.leftchild.insertright(new BinaryTreeNode(14));
head.leftchild.rightchild.insertleft(new BinaryTreeNode(13));
head.leftchild.rightchild.insertright(new BinaryTreeNode(15));
head.rightchild.insertleft(new BinaryTreeNode(17));
head.rightchild.insertright(new BinaryTreeNode(24));

BinaryTreeNode results = return_first_common_ancesstor(
head,head.leftchild.rightchild.leftchild,head.rightchild.leftchild);
System.out.println(results.value);



}

}

It seems that we could use post-order traversal of the binary tree to solve the problem. A c++ solution could be like below:

Node *find_lowest_common_ancestor(N ode * root, Node *node1, Node *node2, int &flag) {
  if (node1 == node2) {
    return node1;
  }
  if (root == NULL) {
    flag = 0;
    return NULL;
  }
  else if (root == node1) {
    flag = 1;
    return NULL;
  }
  else if (root == node2) {
    flag = 2;
    return NULL;
  } 
  int flag1, flag2;
  Node *retNode1 = find_lowest_common_ancestor(root->left, flag1);
  if (retNode1 != NULL) {
    return retNode1;
  } 
  Node *retNode2 = find_lowest_common_ancestor(root->right, flag2);
  if (retNode2 != NULL) {
    return retNode2;
  }
  if (flag1 == 1 && flag2 == 2 || flag1 == 2 && flag2 == 1) {
    return root;
  }
  flag = flag1 + flag2;
  return NULL;
}

You have a Binary Tree and Two node p , q.
You have to find the first common parent of p and q.

tree_node_type *LowestCommonAncestor(
tree_node_type *root , tree_node_type *p , tree_node_type *q)
{
	tree_node_type *l , *r , *temp;
	if(root==NULL)
	{
		return NULL;
	}

	if(root->left==p || root->left==q || root->right ==p || root->right ==q)
	{
		return root;
	}
	else
	{
		l=LowestCommonAncestor(root->left , p , q);
		r=LowestCommonAncestor(root->right , p, q);

		if(l!=NULL && r!=NULL)
		{
			return root;
		}
		else
		{
			temp = (l!=NULL)?l:r;
			return temp;
		}
	}
}

DFS

Initialise a And b to Zero In Main Program

Com_Anc(struct Node *root, struct Node *p, struct Node *q, int &a, int &b){
struct Node *temp ;
if(root){
if(! (*a) && root == p)
*a = 1;

if(! (*b) && root == q)
*b = 1;

if(!(a&&b)){
if(root->l)
temp = Com_Anc(root->l, p, q, a, b);
if(root->r)
temp = Com_Anc(root->r, p, q, a, b);
}

if(a&&b) return root;
else return NULL;
}
return NULL;
}

Initialise a And b to Zero In Main Program

Com_Anc(struct Node *root, struct Node *p, struct Node *q, int &a, int &b){
struct Node *temp ;
if(root){
if(! (*a) && root == p)
*a = 1;

if(! (*b) && root == q)
*b = 1;

if(!(a&&b)){
if(root->l)
temp = Com_Anc(root->l, p, q, a, b);
if(root->r && !(a&&b))
temp = Com_Anc(root->r, p, q, a, b);
}

if(a&&b) return root;
else return temp;
}
return NULL;
}

There are two approaches that could work here:
1) Starting from the root node, recursively determine whether the children belong to the same branch or different branche. If same, then you walk along that branch, if different, the root is your Lowest common ancestor.
2) Find a list of all the parents from the root to each child. And then iterate through them from the top level to bottom level, you result lies in the one before when it becomes unequal to each other.

1. Start with the root compare both nodes data with root if one is smaller and other is larger than root then root is answer. 2.else move the left or right branch where the data lies and repeat step 1 and so on.

node* lowestCommonAncestor(node *root, node *n1, node*n2)
{
  if(root==NULL)
    return NULL;
  else if((n1==root) || (n2==root))
    return root;
  node *itr = root;
  while(itr != NULL)
  {
    if(itr->val < n1->val && itr->val <n2->val)
      itr=itr->right;
    else if (itr->val > n1->val && itr->val  > n2->val)
      itr=itr->left;
    else
      return itr;
  }
}

Idea is to find the node where one node value is larger then the other node value.

tNode* binaryTree::__findComAnsc(tNode * root, tNode * a, tNode * b)
{
    if(root == NULL)
        return NULL;

    if(root == a)
        return root;

    if(root == b)
        return root;

    tNode * n1 = __findComAnsc(root->left, a, b);
    tNode * n2 = __findComAnsc(root->right, a, b);

    if(n1 && n2)
        return root;
    else if(n1 && !n2)
        return n1;
    else if(!n1 && n2)
        return n2;
    else if(n1 == n2)
        return n1;
    else
        return NULL;
}

Node* LCA_itr(Node *root, Node *n1, Node  *n2){
        while(root!=NULL){
                if(root->val==n1->val || root->val==n2->val){
                        return root;
                }
                if((root->val > n1->val && root->val < n2->val) || (root->val < n1->val && root->val > n2->val)){
                        return root;
                }
                if(root->val > n1 && root->val > n2->val){
                        root=root->left;
                }
                if(root->val < n1->val && root->val < n2->val){
                        root=root->right;
                }
        }
        return NULL;
}