Google Interview Question for Software Engineer / Developers


Country: India




Comment hidden because of low score. Click to expand.
8
of 10 vote

Please can someone elagorate the question properly. It is unclear.

- Anonymous May 01, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
2
of 2 vote

int ancestors(tree *root, tree *node)
{
	// how do I call a root an ancestor of the child, 
	// it can either be a direct parent or a children 
	// of its children.

	if( !root || !node)
	{ 
		return 0;
	}
	if (root->left == node || 
		root->right == node || 
		ancestors(root->right) || 
		ancestors(root->left))
		// if I'm the direct ancestor of that node
		// or if any of my children is the ancestor
	// I print myself.
	{
		printf("\n %d", root->data);
		return 1;
	}

return 0;
}

- code_monkey October 16, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

What's the definition of "all" common ancestors?

- Anonymous April 30, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 2 vote

It reminds me of an earlier question about binary search tree. The tentative answer is provided below.

bool comAncestor (Tree *tree) {
       if (tree == null) { return false;}
    
       if (comAncestor(tree->left) && comAncestor(tree->right)) {
           cout << tree->value << "  ";
       }
       return true;
}

- Daru April 30, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Common Ancestor of given two nodes ...sorry for inconvenience...

for eg

1
2 3

4 5 6 7
8 9

common ancestor of 8 and 5 is 1 and 2

so o/t shld be 1, 2

- NaiveCoder May 01, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I hope the question is like this.

Given a Binary Tree ( Not a binary search tree), and values/data of two nodes, find all the common ancestors.

Algorith.
1) Write a recursive function to get reference to two given nodes traversing from root node.
2) Now consider one of the node, and traverse up the tree till node, and pushing all the parent reference to a vector.
3) Now consider the other node, and up up the tree, at each step search for its parent in the vector created in step 2.
4) At a given point if search of step 3 matches, return all the elements in the rest of vector from the point the reference found, as common ancestor.

- Vijay Rajanna May 01, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

U don't have parent pointer....
and u don't have extra space...

- NaiveCoder May 01, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

According to me recursion doesn't come in extra space....

- Puneet August 29, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

do a binary search for the given two value a, b
print each traversed node from root until we meet a node c whose value lies in between a and b

- Anonymous May 01, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

It is a binary tree and not a binary search tree. Hence it will not work.

- Jaiprakash May 01, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 2 vote

Since the problem doesn't say that you cannot modify the tree.
Find both elements in tree and note their node pointers. Now, do a post order traversal where you convert the tree into a structure where each node's left ptr points to its parent.
Now it's simple finding out the intersection of the two linked list which start at the previously noted values

- gbhati May 01, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 2 vote

community.topcoder.com/tc?module=Static&d1=tutorials&d2=lowestCommonAncestor#Reduction from LCA to RMQ

- GoogleCandidate May 02, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

That uses lots of extra space. It basically preprocesses the tree in linear time and allow future lca queries to be done in *constant* time. Very cool algorithm, just doesn't answer the question.

- JC May 03, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

first find both nodes are thre in the tree.if they are, then start traversing both from the root and printing the values values of nodes till they differ... :D

- bharatkrarya@yahoo.co.in May 02, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I guess i am not using extra space and complexity is O(n)

#include<stdio.h>
#include<stdlib.h>

struct node {
int data;
struct node *left;
struct node *right;
};
struct node *root;
struct node * NewNode(int n)
{
struct node *tmp=(struct node *)malloc(sizeof(struct node));
tmp->data=n;
tmp->left=NULL;
tmp->right=NULL;
return tmp;
}
void PreOrder(struct node *root)
{
if(root!=NULL)
{
printf("%d ",root->data);
PreOrder(root->left);
PreOrder(root->right);
}
}

int PrintAncestor(struct node *root,struct node *T1)
{
if(root==NULL)
return 0;
if(T1==NULL)
return 0;

if(root->data==T1->data || PrintAncestor(root->left,T1)||PrintAncestor(root->right,T1))
{
printf("%d ",root->data);
return 1;
}
else
return 0;

}

int PrintCommonAncestor(struct node *root,struct node *T1,struct node *T2)
{
if(root==NULL)
return 0;

int lc=PrintCommonAncestor(root->left,T1,T2);
int rc=PrintCommonAncestor(root->right,T1,T2);

if(root->data==T1->data || root->data==T2->data) // return total count
return (1+lc+rc);

if(lc==0&&rc==0) //if this subtree doesn't have either T1 or T2 i am not a part of ancestor
return 0;

if(lc==1&&rc==1) //this subtree has both T1 and T2 in left as well as right this is lowest common ancestor
{
printf("%d ",root->data);
return 2;
}

else if(lc==2||rc==2) // this subtree has one side both node pass this info to parent, and i am one of the ancestor
{
printf("%d ",root->data);
return 2;
}
else if((lc==1&&rc==0) || (lc==0&&rc==1)) //i just got one node in my sub tree so i can't be ancestor
return 1;
// return 0;
}

int main()
{
root=NewNode(1);
root->left=NewNode(2);
root->right=NewNode(3);
root->left->left=NewNode(4);
root->left->right=NewNode(5);
root->left->left->left=NewNode(8);
root->left->left->right=NewNode(9);
root->right->left=NewNode(6);
root->right->right=NewNode(7);
//PreOrder(root);

// PrintAncestor(root,root->left->left->right);
PrintCommonAncestor(root,root->left->left->left,root);
getchar();
return 0;
}

- Coder May 03, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I have simplified your algorithm bit
int printAllcommonAncestor(TreeNode head,TreeNode node1,TreeNode node2)
{
if (head == null)
return 0;

int lc = printAllcommonAncestor(head.lNode, node1, node2);
int rc = printAllcommonAncestor(head.rNode, node1, node2);

if (head.data == node1.data || head.data == node2.data)
return (1 + lc + rc);

if (lc + rc == 0)
return 0;

if ( (lc + rc ) == 2)
{
Console.Write(" "+ head.data);
return 2;
}
else if ((lc+rc) == 1)
return 1;
return 0;
}

- Arasu June 15, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

No extra space is used if the linked list stores the result doesn't count.

Algorithm:
start from the root
1. if root = seed1 || root = seed2, then return null
2. if seed1 and seed2 are in the same sub tree of root, do the recursion of the function and return the list
3. if seed1 and seed2 are in different sub tree, just return root
4. other cases return null

code:

Public List<Node> findAncestor(Node root, Node seed1, Node seed2) {
If(root == seed1 || root == seed2) {
Return null;
} else {
List<Node> ancestor = new LinkedList<Node>();
Boolean has1 = false;
Boolean has2 = false;
If(root.left != null) {
If(inTheTree(root.left,seed1) && inTheTree(root.left,seed2)) {
Ancestor.add(root);
List<Node> subancestor = findAncestor(root.left,seed1,seed2);
Ancestor.copyAll(subancestor);
Return ancestor;
} else if(!inTheTree(root.left,seed1) && !inTheTree(root.left,seed2)) {
If(root.right == null) {
Return null;
} else {
If(inTheTree(root.left,seed1) { has1 = true;}
If(inTheTree(root.left,seed2) { has2 = true;}
}
}
}
If(root.right != null) {
If(has1 || has2) {
If(has1) {
If(inTheTree(root.right,seed2)) {
Ancestor.add(root);
Return ancestor;
} else {
Return null;
}
} else {
If(InTheTree(root.right, seed1)) {
Ancestor.add(root);
Return ancestor;
} else {
Return null;
}
}
} Else If(inTheTree(root.right,seed1) && inTheTree(root.right,seed2)) {
Ancestor.add(root);
List<Node> subancestor = findAncestor(root.right,seed1,seed2);
Ancestor.copyAll(subancestor);
Return ancestor;
} else {
Return null;
}
}
Return null;
}
}
Public boolean inTheTree(Node root, Node seed) {
if(root == null) {
return null;
} else if(root == seed) {
Return true;
} else {
If(inTheTree(root.left,seed) || inTheTree(root.right.seed)) {
Return true;
} else {
Return false;
}
}
}

- Daisy G May 05, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Calling inTheTree for each node, that is not O(n), it's O(nlgn)

- racolas June 06, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

void traverse(node *Node){

if(Node->left!=null)
traverse(Node->left);

if(Node->right!=null)
traverse(Node->right);

if(Element1 & Element2) print(Node);
else {
if(Node->data == Element1Data) Element1=true;
else if(Node->data==ElementData)Element2=true;
}
}

- lohith May 05, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

for a binary tree, I think finding a common ancestor through recursion will take a lot more time than O(n)

- DashDash May 13, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

void find_common_ancestor(Node *root, Node *a, Node *b)
{
    check_ab(root, a, b);
}

int check_ab(Node *root, Node *a, Node *b) {
   int status;
   if(root == NULL) return 0;
   else if(root == a) return 1;
   else if(root == b) return 2;  
   status = check_ab(root->left) | check_ab(root->right);
   if(status == 3) {print_node(root);}
   return status;
}

- jzhu May 17, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

This code fails when one of a or b is the ancestor of the other. Otherwise, clean code. Also, the two recursive calls miss arguments a, b.

- -db July 30, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Quite similar to the question in the book "Cracking the coding interview". Just did a small change. but don't know whether it is O(n).
public static Node commonAncestor(Node root, Node p, Node q){

System.out.print(root.value + "->");
if (covers(root.left, p) && covers(root.left, q)){
return commonAncestor(root.left, p, q);
}
if (covers(root.right, p) && covers(root.right, q)){
return commonAncestor(root.right, p, q);

}

return root;
}

private static boolean covers(Node root, Node p){
if (root == null) return false;
if (root == p) return true;
return covers(root.left, p) || covers(root.right, p);
}

- eboyGTK May 18, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Quite similar to the question in the book "Cracking the coding interview". Just did a small change. but don't know whether it is O(n).
public static Node commonAncestor(Node root, Node p, Node q){

System.out.print(root.value + "->");
if (covers(root.left, p) && covers(root.left, q)){
return commonAncestor(root.left, p, q);
}
if (covers(root.right, p) && covers(root.right, q)){
return commonAncestor(root.right, p, q);

}

return root;
}

private static boolean covers(Node root, Node p){
if (root == null) return false;
if (root == p) return true;
return covers(root.left, p) || covers(root.right, p);
}

- eboyGTK May 18, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <stdio.h>
#include <stdlib.h>

typedef struct BST_ {
int data;
struct BST_ *left;
struct BST_ *right;
} BST;

int traverse(BST *t, int x, int y)
{
int found1 = 0;
int found2 = 0;
int found_below1;
int found_below2;
int found_below;

if (t == NULL)
return 0;

if (t->data == x) {
found1 = 1;
}
if (t->data == y) {
found2 = 1;
}

found_below = traverse(t->left, x, y);
found_below |= traverse(t->right, x, y);

found_below1 = found_below & 0xff;
found_below2 = found_below >> 8 & 0xff;

if (found_below1 && found_below2) {
printf("%d ", t->data);
}

int ret = (found2 | found_below2) << 8 |
found1 | found_below1;
return ret;
}

main()
{
BST *x1 = (BST *) malloc(sizeof(BST));
BST *x2 = (BST *) malloc(sizeof(BST));
BST *x3 = (BST *) malloc(sizeof(BST));
BST *x4 = (BST *) malloc(sizeof(BST));
BST *x5 = (BST *) malloc(sizeof(BST));
BST *x6 = (BST *) malloc(sizeof(BST));
BST *x7 = (BST *) malloc(sizeof(BST));
x1->data = 1;
x1->left = x2;
x1->right = x3;

x2->data = 2;
x2->left = x4;
x2->right = x5;

x3->data = 3;
x3->left = x6;
x3->right = x7;

x4->data = 4;
x4->left = NULL;
x4->right = NULL;

x5->data = 5;
x5->left = NULL;
x5->right = NULL;

x6->data = 6;
x6->left = NULL;
x6->right = NULL;

x7->data = 7;
x7->left = NULL;
x7->right = NULL;

traverse(x1, 6, 7);
printf("\n");

free(x1);
free(x2);
free(x3);
free(x4);
free(x5);
free(x6);
free(x7);
}

- Victor May 24, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <stdio.h>
#include <stdlib.h>

typedef struct BST_ {
int data;
struct BST_ *left;
struct BST_ *right;
} BST;

int traverse(BST *t, int x, int y)
{
int found1 = 0;
int found2 = 0;
int found_below1;
int found_below2;
int found_below;

if (t == NULL)
return 0;

if (t->data == x) {
found1 = 1;
}
if (t->data == y) {
found2 = 1;
}

found_below = traverse(t->left, x, y);
found_below |= traverse(t->right, x, y);

found_below1 = found_below & 0xff;
found_below2 = found_below >> 8 & 0xff;

if (found_below1 && found_below2) {
printf("%d ", t->data);
}

int ret = (found2 | found_below2) << 8 |
found1 | found_below1;
return ret;
}

main()
{
BST *x1 = (BST *) malloc(sizeof(BST));
BST *x2 = (BST *) malloc(sizeof(BST));
BST *x3 = (BST *) malloc(sizeof(BST));
BST *x4 = (BST *) malloc(sizeof(BST));
BST *x5 = (BST *) malloc(sizeof(BST));
BST *x6 = (BST *) malloc(sizeof(BST));
BST *x7 = (BST *) malloc(sizeof(BST));
x1->data = 1;
x1->left = x2;
x1->right = x3;

x2->data = 2;
x2->left = x4;
x2->right = x5;

x3->data = 3;
x3->left = x6;
x3->right = x7;

x4->data = 4;
x4->left = NULL;
x4->right = NULL;

x5->data = 5;
x5->left = NULL;
x5->right = NULL;

x6->data = 6;
x6->left = NULL;
x6->right = NULL;

x7->data = 7;
x7->left = NULL;
x7->right = NULL;

traverse(x1, 6, 7);
printf("\n");

free(x1);
free(x2);
free(x3);
free(x4);
free(x5);
free(x6);
free(x7);
}

- Victor May 24, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 4 vote

Please confirm algorithm.

First find the lowest common ancestor of the 2 given nodes. Use the property of the BST that right child key > parent key > left child key. Since the root has a path to any node, start there.

If both keys are less than the root, go to the left subtree; if both keys are greater, go right. If the root key is between them, you've found the lowest common ancestor.

For going left/right, recursively iterate and repeat this comparison with your current node until you traverse to a node where its key is between the given 2 keys. Then as you recursively go back up the tree, return all parent nodes to give you back all common ancestors.

No extra space is used. Worst case is you traverse all the way down to the leaf level to find the lowest common ancestor. So time complexity is O(logn).

- alchu8 May 24, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

The question only says binary tree.

- racolas June 06, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

www[.]geeksforgeeks.org/archives/1029 awesome code + explanation

- addict June 04, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

That's for a binary *SEARCH* tree, this question is about a binary tree.

- racolas June 06, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

logic, an last ancestor is the one whose left child is smaller than parent and right child bigger than parent.
this is O(logn)

printAncestor(root, a, b) {

      if (root == NULL)
          return;
      else {
              if (root->data > a && root->data > b)
                      printf(root->data);
                      printAncestor(root->left, a, b);
              } else if (root->data < a && root->data < b) {
                      printf(root->data);
                      printAncestor(root->right, a, b);
              } else if (root->data > a && root->data < b) {
                      printf("Last Ancestor", root->data);
                      printAncestor(root->left, a, b);
               }

- maddy June 12, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I have simplified Coder's script and translated in c#

int printAllcommonAncestor(TreeNode head,TreeNode node1,TreeNode node2)
{
if (head == null || node1==null || node2==null)
return 0;

int lc = printAllcommonAncestor(head.lNode, node1, node2);
int rc = printAllcommonAncestor(head.rNode, node1, node2);

if (head.data == node1.data || head.data == node2.data)
return (1 + lc + rc);

if ( (lc + rc ) == 2)
Console.Write(" "+ head.data);
return ( lc + rc );
}

- Arasu June 15, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static void printCommonAncestors(final Node head, final int n1, final int n2)
    {
        traverse(head, n1, n2);
    }
    
    private static int traverse(final Node head, final int n1, final int n2)
    {
        int r1 = head.getLeft() != null ? traverse(head.getLeft(), n1, n2) : 0;
        int r2 = head.getRight() != null ? traverse(head.getRight(), n1, n2) : 0;
        int r3 = head.getData() == n1 ? 1 : 0;
        r3 += (head.getData() == n2 ? 1 : 0);
        
        if(r1 + r2  == 2)
        {
            System.out.print(head.getData() + " ");
        }
        return r1 + r2 + r3;
    }

- Anonymous June 17, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

void main()
{
    Node *r, *a, *b; // r is the root of the tree. a and b are the two nodes to find.
    ... // construct tree having r as root

    bool fa, fb;     // fa: found a, fb: found b.
    fa = fb = false;
    f1(r,a,b,&fa,&fb);
}

void f1(Node *r, Node *a, Node *b, bool *fa, bool *fb)
{
    if(r==null || a==null || b==null)
       return false;

    if(r==a) 
    {
       *fa = true;
    }

    if(r==b) 
    {
       *fb = true;
    }
 
    bool fa1, fb1;
    fa1 = fb1 = false;

    f1(r->left, a, b, &fa1, &fb1);
    *fa |= fa1;
    *fb |= fb1;
    
    if(!*fa || !*fb) // if a or b is not found, search right child.
    {
       fa1 = fb1 = false;
       f2(r->right, a, b, &fa1, &fb1);
       *fa |= fa1;
       *fb |= fb1;
    }

    if(*fa && *fb) // if found both a and b, print r.
    {
        print(r);
    }    
}

- jiangok2006 July 17, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Do a preorder traversal of the tree. Keep a counter found of how many nodes have been discovered so far. A node is an ancestor of both a and b only if found is 0 upon entering the procedure call and 2 after the 2 recursive calls returns.

if a is an ancestor of b, then a is an ancestor of both a and b.

code tested.

void findAllCommonAncestors(Node * root, int a, int b, int & found) {
    if (NULL == root)
        return;
    int oldfound = found;
    if (a == root->d || b == root->d) {
        found++;
        if (2 == found)
            return;
    }
    findAllCommonAncestors(root->left, a, b, found);
    if (2 == found && 0 == oldfound) {
        cout << root->d << " ";
        return;
    }
    findAllCommonAncestors(root->right, a, b, found);
    if (2 == found && 0 == oldfound) {
        cout << root->d << " ";
        return;
    }
}

- - db July 30, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static int printAllCommonAncestor(TreeNode root, TreeNode n1, TreeNode n2) {
		if (root == null) return 0;
		if (root == n1) return 1;
		if (root == n2) return 1;
		
		int sum = printAllCommonAncestor(root.left, n1, n2) + printAllCommonAncestor(root.right, n1, n2);
		if (sum == 2)
			System.out.println(root.data);
		
		return sum;
	}

- Anonymous August 04, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

int All_common_ancestor(NODE *Tree, NODE *Node1, NODE *Node2){
    if(!Tree) return 0;
    if(!search(Tree, Node1) && !search(Tree, Node2)) return 0;
    
    if(Tree->info == Node1->info || Tree->info == Node2->info){
        if(Tree->info == Node1->info){
            if(search(Tree->left, Node2) || search(Tree->right, Node2)){
                print Tree->info;
                return 2;
            }
        } else if(Tree->info == Node2->info) {
            if(search(Tree->left, Node1) || search(Tree->right, Node1)){
                print Tree->info;
                return 2;
            }
        } else
            return 1;
    }else{
        int L = 0, R = 0;
        L = All_common_ancestor(Tree->Left, Node1, Node2);
        R = All_common_ancestor(Tree->Right, Node1, Node2);
        if(L & R){
            print Tree->info;
            return 2;
        } else if (L==2 || R==2){
            print Tree->info;
            return 2;
        } else if(L||R) {
            return 1;
        } else {
            return 0;
        }
    }
}

BOOL search(NODE *Tree, NODE *Node){
    if(!Tree) return 0;
    if(Tree->info == Node->info)
        return 1;
    else
        return search(Tree->left, Node) || search(Tree->right, Node);
}

- SRB August 19, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class A {

	private Node head = new Node();

	public static void main(String[] args) {
	
		// Initialize the binary tree
		// Read two nodes that need to be checked for common ancestors		
		Node node1;
		Node node2;
		
		// Assumes that node1 and node2 actually exist in the tree
		printCommonAncestors(head, node1, node2, false, false);
	
	}
	
	private static boolean printCommonAncestors(Node currentNode, Node node1, Node node2, boolean node1Found, boolean node2Found) {

		boolean isCommonAncestor = false;
		
		if (currentNode != null) {

			// Check whether the current node is equal to the first node.
			// If yes, set the first node found = true.
			if (!node1Found && currentNode.value == node1.value) {
				node1Found = true;
			}
			
			// Check whether the current node is equal to the second node.
			// If yes, set the second node found = true.
			if (!node2Found && currentNode.value == node2.value) {
				node2Found = true;
			}
	
			// If at least one of the nodes is not found, proceed with the subtrees
			if (!node1Found || !node2Found) {
				
				// If common ancestors weren't found yet, then proceed with the left subtree
				isCommonAncestor = printCommonAncestors(currentNode.left, node1, node2, node1Found, node2Found);
				
				// If common ancestors found, then print the current node.
				// Else, proceed with the right subtree.
				if (isCommonAncestor) {
					System.out.println(currentNode);
				} else {
					isCommonAncestor = printCommonAncestors(currentNode.right, node1, node2, node1Found, node2Found);
					if (isCommonAncestor) {
						System.out.println(currentNode);
					}
				}
			} else {
				isCommonAncestor = true;
			}
		}

		return isCommonAncestor;

	}
}

- Anonymous September 09, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

The following solution works for any n-ary tree, not necessarily balanced or even a search tree :
1) Find out the depths of the two nodes, say n1 and n2 by blindly traversing up till the root. Lets say the depths come out to be d1 and d2.
2) If the depths are the same then go to step 4) else go to step 3) (assume that d1 > d2 w.l.o.g.)
3) For d1 - d2 steps n1 <= parent(n1)
4) Till parent(n1) != parent(n2), n1 <= parent(n1), n2 <= parent(n2)

Here the <= operator stands for assignment. The logic behind the algorithm is the following. Given two nodes at the same level in the tree, if we move one step up for both at the time then we are bound to collide at the lowest common ancestor. The problem is that the given nodes might be at different levels which is why in the first step we find the depths and let the deeper node go up till it reaches the level of the shallow node and then continue from thereon.

- purushottam.kar November 04, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

bool printAncestors(TreeNode* root, TreeNode* key)
   {
            if (root == NULL) return false;
            if (root == key ) { return true ; }
            if ( printancestor(root->left, key) |  printancestor(root->right, key))
                            cout << root->val << endl;
            return true;  
            
   }

- Anonymous July 31, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

pair<bool, bool> common_ancestors(TreeNode* root, int x, int y)
{
    if (root == NULL) make_pair(false, false); 
       
    pair<bool, bool> lans = common_ancestors(root->left, x, y);
    pair<bool, bool> rans = common_ancestors(root->right, x, y);
    if (lans.first | rans.first && lans.second || rans.second)
         cout << root->val << endl;
    if (root->val == x) return make_pair(true, lans.second | rans.second);
    if (root->val == y) return make_pair(lans.first | rans.second, true);
}

- Anonymous July 31, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

add 1 more line in the end

return make_pair(lans.first | rans.first, lans.second | rans.second);

- Anonymous July 31, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static int PrintCommonAncestors(Node root, Node n1, Node n2)
        {
            if(root == null)
                return 0;

            if (root == n1 || root == n2 )
            {
                if(n1==n2)
                    return 2;
                else
                    return 1;
            }

            int l = PrintCommonAncestors(root.left, n1, n2);
            int r = PrintCommonAncestors(root.right, n1, n2);

            if (l==1 && r==1||l == 2 || r == 2)
            {
                Console.WriteLine(root.val);
                return 2;
            }

            return l+r;
        }

- bp September 12, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I believe the question is to print all the common ancestors two nodes have in a binary tree. Below is a recursive solution for the same with worst case complexity is O(n):

void printCommonAncestors(Node *root, int a, int b, bool *aFound, bool *bFound)
{
	if(!root)
		return;
		
	if(root->data == a)
	{
		*aFound = true; // I have found a
		if(!*bFound) // Now I have to search for b below a
		{
			printCommonAncestors(root->left, b, b, aFound, bFound); // both elements set as b
			if(*bFound) // If b is found on a's left subtree
				cout << root->data << " ";
			else
			{
				printCommonAncestors(root->right, b, b, aFound, bFound);
				if(*bFound) // If b is found on a's right subtree
					cout << root->data << " ";
			}
		}
	}
	else if(root->data == b) // same things like above for b
	{
		*bFound = true;
		if(!*aFound)
		{
			printCommonAncestors(root->left, a, a, aFound, bFound);
			if(*aFound)
				cout << root->data << " ";
			else
			{
				printCommonAncestors(root->right, a, a, aFound, bFound);
				if(*aFound)
					cout << root->data << " ";
			}
		}
	}
	else // a node is a common ancestor if both a & b are found below it
	{
		printCommonAncestors(root->left, a, b, aFound, bFound);
		if(*aFound && *bFound)
			cout << root->data << " ";
		else
		{
			printCommonAncestors(root->right, a, b, aFound, bFound);
			if(*aFound && *bFound)
				cout << root->data << " ";
		}
	}
}

N.B. Though the solution doesn't use any explicit extra space, but it will definitely require O(n) stack space in worst case due to recursion.

- Sunny Mitra June 17, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

All non-leaf nodes will be common ancestors, just print 'em O(n)

- Second Attempt September 08, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Consider this structure

5
	8				6
3		2		1		9

If you want to check for 8 and 2, based on your assumption, 8, 5, and 6 are common ancestors, which is not the case as 6 is not a common ancestor.

- Prash September 09, 2012 | Flag


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More