Amazon Interview Question
SDE1sTeam: Bangalore
Country: India
Interview Type: In-Person
can career cup stop people from uploading code longer than 10 lines please? Holy cow:) how long did you think about this?
The simple mirroring is easy here is the solution for alternate mirroring
//Initial value for level is 1 i.e root
void alterMirror(Node noot, int level){
if(root==null)
return;
if(level%2==0){
Node tem = root.left;
root.right = root.left;
root.left = temp;
}
level++;
alterMirroe(root.left,level)
alterMirror(root.right,level);
}
}
Iterative version for same ...................... use one structure to keep track of level and nodes
struct lvlnode {
int lvl;
struct node *no;
};
void mirror1(struct node *t){
if(t==NULL ) return ;
stack<struct lvlnode > s1;
struct lvlnode l;
l.no=t;
l.lvl=1;
s1.push(l);
struct lvlnode t1;
stack<struct lvlnode> s2;
while(!s1.empty()){
t1=s1.top();
s1.pop();
s2.push(t1);
t=t1.no;
if(t->left){
t1.no=t->left;
t1.lvl=t1.lvl+1;
s1.push(t1);
}
if(t->right){
t1.no=t->right;
t1.lvl=t1.lvl+1;
s1.push(t1);
}
}
while(!s2.empty()){
struct node *temp;
t1=s2.top();
s2.pop();
int level=t1.lvl;
struct node *a=t1.no;
if(level %2 ==0){
temp=a->left;
a->left=a->right;
a->right=temp;
}
}
}
Build a array from the traversal of binary tree.Swap the elements present at index 2^i to 2^(i+1)-1 where i is odd.Then construct the tree from the queue.
void MirrorAlternateWrapper(Node root){
if( root != null){
mirrorAlternate(root, 0);
}
}
void mirrorAlternate(Node root, int level){
if(root == null) return;
mirrorAlternate(root.left, level+1);
mirrorAlternate(root.right, level+1);
if(level %2 == 0){
Node temp = root.right;
root.right = root.left;
root.left = temp;
}
}
Mirroring alternate levels
struct node* mirror_alternate_levels(struct node* tree,int level)
{
if(tree==NULL)
return NULL;
else
{
struct node* l=mirror_alternate_levels(tree->left,level+1);
struct node* r=mirror_alternate_levels(tree->right,level+1);
if(level%2==0)
{
tree->left=r;
tree->right=l;
}
else
{
tree->left=l;
tree->right=r;
}
}
}
This one is the code using recursion
#include <stdio.h>
#include <conio.h>
#include <malloc.h>
typedef struct tree tree_t;
struct tree
{
int data;
tree_t *left;
tree_t *right;
};
tree_t *newNode(int data)
{
tree_t *n=(tree_t *)malloc(sizeof(tree_t));
n->data=data;
n->left=n->right=NULL;
return n;
}
void preorder(tree_t *root)
{
if(root==NULL)
return;
printf(" %d ",root->data);
preorder(root->left);
preorder(root->right);
}
void mirror(tree_t *t)
{
if(t==NULL)
return;
else
{
tree_t *temp;
mirror(t->left);
mirror(t->right);
temp=t->left;
t->left=t->right;
t->right=temp;
}
}
void mirrorAlt(tree_t *t)
{
if(t==NULL)
{
return;
}
else
{
tree_t *temp=t->left;
t->left=t->right;
t->right=temp;
if(t->left==NULL&&t->right==NULL)
return;
else if(t->left!=NULL&&t->right==NULL)
mirrorAlt(t->left->left);
else if(t->right!=NULL&&t->left==NULL)
mirrorAlt(t->right->right);
else
{
mirrorAlt(t->left->left);
mirrorAlt(t->right->right);
}
return;
}
}
int main()
{
tree_t *root=newNode(1);
root->left=newNode(2);
root->left->left=newNode(4);
root->left->right=newNode(5);
root->left->right->left=newNode(6);
root->left->right->right=newNode(7);
root->right=newNode(3);
printf(" Mirror of the tree preorder\n");
mirror(root);
preorder(root);
printf("\nMirror at alternate levels preorder\n");
mirrorAlt(root);
preorder(root);
}
Paste the code and print it. You will get the nodes mirrored at alternate levels. Actually i am recursively passing root->left->left to pass one level down from the current node that is alternate levels similarly root->right->right to get the alternate level in the right side. This further extends down to the below node recursively thus accounting for alternate levels at the next node.
- Anonymous July 16, 2013