CareerCup

http://en.wikipedia.org/wiki/Lowest_common_ancestor

As i guess, here we need to find the closest ancestor of two nodes!
The following fun should work fine.
Suppose wer have to find the closest ancestor for the nodes p and q..
tree * closeestAncestor(tree * root, tree *p, tree *q)
{
tree *l,*r;
if(root == NULL)
return NULL;
if(root->left==p||root->right==p||root->left==q||root->left==q)
return root;
else
{
l = closeestAncestor(root->left,p,q);
r = closeestAncestor(root->right,p,q);
if(l!=NULL&&r!=NULL)
return root;
return (l!=NULL?l:r);
}
}

Ratn,

if(root->left==p||root->right==p||root->left==q||root->right==q)

Can you add slight description to the above code.

As we need ancestors, Duplicate keys shouldn't give problem

Let us assume these are nodes,Please let us know about the approach.

Assume TreeNode* root, and two value *p, *q given, tree contains N nodes.
1) If ThreeNode includes a father pointer, then the path between root and p can be found easily(logN), path between q and root as well, given path[root, p] and [root,q], find a common point

2) If no father point, we are looking for path also. Depth-first-search, record the current path every step(a heap? Push when going deeper, pop afterward), a different from above solution is that once we get the two paths we need: [root,p] and [root,q], break DFS immediatly, that really saves some time for some cases, e.g. *p and *q are both near root, but some other branches could be deep.
Root
P n1
q n2
n3 n4
..........

private void findCommonNode(int node1, int node2){

Node cur = root;

if(root == null){
System.out.println("Empty Tree!");
return;
}

int high, low;

high = Math.max(node1,node2);
low = Math.min(node1, node2);

while(cur.right != null && cur.data < low){
cur = cur.right;
}
while(cur.left != null && cur.data > high){
cur=cur.left;
}
if(cur != null)
System.out.println(cur.data);

}

If its a BST, use the values to check. First number whose value is in between the given numbers is the LCA. Else, use dynamic programming, reduction method.

If BST, then O(n) time and O(1) space, else O(n) time and space

I am assuming that this is a binary tree with no duplicates.


/* child1 and child2 contains the value of nodes
* whose common ancestor has to be found.
*/
Node *findAncestor(Node *head, int child1, int child2)
{
isPresent isFirst=FALSE, isSecond=FALSE;
Node *previous=NULL;
while(head != NULL) {
if(child1 == head->value || child2 == head->value) {
return previous;
}
previous = head;
isFirst = searchTree(head->left, child1);
isSecond = searchTree(head->left, child2);
if(isFirst == TRUE && isSecond == TRUE) {
head = head->left;
continue;
}
if(isFirst == FALSE && isSecond == FALSE) {
head = head->right;
continue;
}
return head;
}
}

isPresent searchTree(Node *head, int n)
{
isPresent rightFound=FALSE, leftFound=FALSE;
if(head == NULL)
return FALSE;
if(head->value == n)
return TRUE;
leftFound = searchTree(head->left, n);
rightFound = searchTree(head->right, n);

if (leftFound == TRUE || rightFound == TRUE)
return TRUE;
else
return FALSE;
}

Algo:
1. Find the parents of the two nodes, parent1 and parent2
2. if parent1.value = parent2.value return parent
3. else continue looking up the tree for parents of parent1 and parent2 and compare their values, till you find the common parent or root, whichever is first.

int minacestor(struct tree *root,int v1,int v2)
{
if(root==NULL)
return 0;
if(v1>root->data && v2>root->data)
minacestor(root->right,v1,v2);
else if(v1<root->data && v2<root->data)
minacestor(root->right,v1,v2);
else
return (root->data);
}

Assuming that nodes with values x and y exist:

Node* LCA(Node* root, int x, int y)
{
Node* temp = root;
while(temp)
{
if(temp->data > x && temp->data > y)
temp = temp->left;
else if(temp->data < x && temp->data < y)
temp = temp->right;
else
return temp;
}
return temp;
}

Assume val1 is less than val2.

Node * FindCommonAncestor(Node * root, int val1, int val2)
{
Node *ancestor;
if(root == NULL || root->data == val1 || root->data == val2)
return NULL;
if(root->data > val1 && root->data < val2)
return root;
else if(root->data < val1)
{
ancestor = FindCommonAncestor(root->right, val1, val2);
}
else if(root->data > val2)
{
ancestor = FindCommonAncestor(root->left, val1, val2);
}

if(ancestor == NULL)
return root;
else
return ancestor;
}

package google;

import java.util.concurrent.ArrayBlockingQueue;

public class CommonAncestor {

private class Node {
int data;
Node left;
Node right;
Node parent;
}

Node root;

private void constructTree(int data) {

if (root == null) {
root = new Node();
root.data = data;
root.left = null;
root.right = null;
root.parent = null;
return;
}

Node cur = root;

while (cur.left != null && data < cur.data) {
cur = cur.left;
}

while (cur.right != null && data > cur.data) {
cur = cur.right;
}

Node temp = new Node();

temp.data = data;
temp.left = null;
temp.right = null;

if (data < cur.data) {
cur.left = temp;
}
else {
cur.right = temp;
}
temp.parent = cur;
}

private void bfs() {

ArrayBlockingQueue<Node> Q = new ArrayBlockingQueue<Node>(20);

if (root == null) {
System.out.println("Invalid Tree!!!");
return;
}

Q.add(root);

while (Q.isEmpty() == false) {

Node tmp = Q.remove();

if (tmp.left != null)
Q.add(tmp.left);

if (tmp.right != null)
Q.add(tmp.right);

System.out.println(tmp.data);
}
}

private void findCommonNode(Node n1 , Node n2){

int node1= n1.data;
int node2 = n2.data;

int low = Math.min(node1, node2);
int high = Math.max(node1, node2);


Node cur = root;

while(high < cur.data && cur.left != null){
cur = cur.left;
}

while(low > cur.data && cur.right != null){
cur = cur.right;
}

assert (!(cur.equals(null)));
System.out.println("The Common Node for Nodes "+ n1.data + " and "+n2.data+" is : "+cur.data);

}

/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub

CommonAncestor obj = new CommonAncestor();
obj.constructTree(5);
obj.constructTree(2);
obj.constructTree(7);
obj.constructTree(1);
obj.constructTree(3);
obj.constructTree(6);
obj.constructTree(9);
obj.bfs();


Node n1 = obj.new Node();
Node n2 = obj.new Node();


n1.data = 3;
n2.data = 1;

obj.findCommonNode(n1, n2);
}

}