Google Interview Question
Software Engineer / DevelopersCountry: India
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;
}
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.
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
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
community.topcoder.com/tc?module=Static&d1=tutorials&d2=lowestCommonAncestor#Reduction from LCA to RMQ
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;
}
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;
}
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;
}
}
}
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;
}
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);
}
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);
}
#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);
}
#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);
}
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).
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);
}
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 );
}
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;
}
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);
}
}
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;
}
}
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;
}
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);
}
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;
}
}
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.
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);
}
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;
}
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.
Please can someone elagorate the question properly. It is unclear.
- Anonymous May 01, 2012