Amazon Interview Question
SDE1sCountry: India
Interview Type: Phone Interview
You can't?
Why not just traverse the tree in order and comparing current, left child and right child with the other tree's current/leftchild/rightchild?
@AnonymousMe, You can compare both trees using inorder traversal
1. Pass both root nodes to the function and iterate them at the same time, compare the nodes, just like @bunnybare mentioned above. (recommended)
2. Alternatively, you can traverse the trees one by one and save the null children as nodes too. e.g., if this is your tree
3
/ \
1 2
/
4
Your in-order will be: null, 4, null, 1, null, 3, null, 2, null
Then compare these two lists.
By comparing both trees together at each step of inorder
#include<stdio.h>
struct node
{
int data;
struct node* left;
struct node* right;
};
struct stack
{
int top;
int capacity;
struct node **array;
};
struct stack * CreateStack()
{
struct stack *s=malloc(sizeof(struct stack));
if(!s)
return 0;
s->top=-1;
s->capacity=10;
s->array=malloc(s->capacity*sizeof(struct node *));
if(!s->array)
return 0;
return s;
}
int isEmptyStack(struct stack *s)
{
return(s->top==-1);
}
void DoubleStack(struct stack *s)
{
s->capacity*=2;
s->array=realloc(s->array,s->capacity);
}
int isFullStack(struct stack *s)
{
return(s->top==s->capacity-1);
}
void push(struct stack *s, struct node *root)
{
if(isFullStack(s))
DoubleStack(s);
s->array[++s->top]=root;
}
struct node * pop(struct stack *s)
{
if(isEmptyStack(s))
return 0;
else
return s->array[s->top--];
}
struct node * newNode(int data)
{
struct node *root;
root=(struct node*)malloc(sizeof(struct node));
root->data=data;
root->left=NULL;
root->right=NULL;
return root;
}
int equalTrees(struct node *root1,struct node *root2)
{
int count1=0,count2=0;
struct stack *s1=CreateStack();
struct stack *s2=CreateStack();
int x=3,y=3;
while(1)
{
while(root2)
{
push(s2,root2);
root2=root2->left;
count2++;
}
while(root1)
{
push(s1,root1);
root1=root1->left;
count1++;
}
if(isEmptyStack(s1) && isEmptyStack(s2))
{
return 1;
}
if(isEmptyStack(s1)|| isEmptyStack(s1) )
{
return 0;
}
if(count1!=count2)
return 0;
root1=pop(s1);
root2=pop(s2);
if(root1->data!=root2->data)
return 0;
root1=root1->right;
root2=root2->right;
}
}
int main()
{
struct node *root1 =newNode(1);
root1->left = newNode(3);
root1->left->right = newNode(2);
struct node *root2 = newNode(1);
root2->left = newNode(2);
root2->left->left = newNode(3);
printf("%d",equalTrees(root1,root2));
return 0;
}
I believe you can. If both Binary tree implementation is using an adjacency matrix then you can use iteration to traverse the tree. The matrix is NxN multi-dimensional array. So for a Binary Tree with 10 nodes you get a A[10][10] to represent the relationship of the nodes, all nodes with a value (say non-negative value) represents relationship from source node to target node. You also need an array which contains the values say V[N].
Note that my assumption here is the binary tree has already allocated the arrays as a representation of the trees and it node values. The problem we are trying to solve is if our comparison require additional space, and my answer is we don't need additional space as long as its represented this way as a tree. Of course you need the iteration variables.
So for example if you have an entry A[1][2] = 1 and A[1][3] = 1 then Node 1 has two children Node 2 and Node 3. Then lookup the values array say V[1], V[2] and V[3] for the values. Just compare these indexes on both the binary trees. If at least one is not equal then exit your iteration and the trees are not equal.
You can use Morris traversal and traverse the trees iteratively using no stack (www.geeksforgeeks.org/inorder-tree-traversal-without-recursion-and-without-stack/)
- oOZz June 17, 2013