Microsoft Interview Question
Software Engineer / DevelopersCountry: United States
according to given constraints we get (a+b)*((c+d)-e)
Constructing parse tree for this :-
*
/ \
+ -
/ \ / \
a b + e
/ \
c d
You can do first Right rotation around * and then Left rotation around the * node and you will get the correct result.
search wiki for the tree rotation.
First Right Rotation around node * and then Left Rotation around node *
* + +
/ \ / \ / \
+ + Left Rotation a * Right Rotation a +
/ \ / \ =====> / \ =====> / \
a b c - b + * -
/ \ / \ / \ / \
e f c - b c e f
/ \
e f
I wrote a c++ version, rotate twice for each *
#include <iostream>
#include <assert.h>
using namespace std;
struct Node;
typedef struct Node * pN;
struct Node {
char data;
pN left;
pN right;
};
void print_tree (pN rootN)
{
if(rootN==NULL) return;
else {
print_tree(rootN->left);
cout<<rootN->data<<" ";
print_tree(rootN->right);
return;
}
}
//rotate right, return the new root
pN rotate_right(pN rootN) {
cout<<"rotate right"<<endl;
if (rootN==NULL || rootN->right == NULL || rootN->left == NULL ) return rootN;
else {
pN lN = rootN->left;// pN rN = rootN->right;
if(lN->left==NULL || lN->right==NULL) //this is just for our case, leaf node cannot be empty -- because there is no such thing as 'NULL+b'
return rootN;
else {
rootN->left = lN->right;
lN->right = rootN;
return lN;
}
}
}
//rotate left, return the new root
pN rotate_left(pN rootN) {
cout<<"rotate left"<<endl;
if (rootN==NULL || rootN->right == NULL || rootN->left == NULL ) return rootN;
else {
// pN lN = rootN->left;
pN rN = rootN->right;
if(rN->left==NULL || rN->right==NULL) //this is just for our case, leaf node cannot be empty -- because there is no such thing as 'NULL+b'
return rootN;
else {
rootN->right = rN->left;
rN->left = rootN;
return rN;
}
}
}
//correct the tree by rotating, return the new root
pN myf (pN rootN) {
if (rootN==NULL) return NULL;
else {
cout<<"work on node "<<rootN->data<<endl;
pN newleft=NULL; pN newright=NULL;
if (rootN->left) {
newleft = myf(rootN->left);
cout<<"new left subtree: "<<endl;
print_tree(newleft); cout<<endl; }
if (rootN->right) {
newright = myf(rootN->right);
cout<<"new right subtree: "<<endl;
print_tree(newright); cout<<endl; }
rootN->left = newleft;
rootN->right = newright;
if (rootN->data == '*' )
{
cout<<"now rotate node * "<<endl;
assert(newleft); assert(newright);
pN newroot_rr = rotate_right(rootN);
pN newroot_rl = rotate_left(newroot_rr);
return newroot_rl;
}
else return rootN;
}
}
void init_node (pN newnode, char newdata, pN l, pN r) {
newnode->data = newdata;
newnode->left = l;
newnode->right = r;
return;
}
int main() {
pN mynode1 = (pN)calloc(1,sizeof(Node));
init_node(mynode1,'a',NULL,NULL);
pN mynode2 = (pN)calloc(1,sizeof(Node));
init_node(mynode2,'b',NULL,NULL);
pN mynode3 = (pN)calloc(1,sizeof(Node));
init_node(mynode3,'c',NULL,NULL);
pN mynode4 = (pN)calloc(1,sizeof(Node));
init_node(mynode4,'d',NULL,NULL);
pN mynode5 = (pN)calloc(1,sizeof(Node));
init_node(mynode5,'e',NULL,NULL);
pN mynode6 = (pN)calloc(1,sizeof(Node)); //a+b
init_node(mynode6,'+',mynode1,mynode2);
pN mynode7 = (pN)calloc(1,sizeof(Node)); //d-e
init_node(mynode7,'-',mynode4,mynode5);
pN mynode8 = (pN)calloc(1,sizeof(Node)); //c+(d-e)
init_node(mynode8,'+',mynode3,mynode7);
pN mynode9 = (pN)calloc(1,sizeof(Node));
init_node(mynode9,'*',mynode6,mynode8);
cout<<"check original tree :"<<endl;
print_tree(mynode9);
pN newroot = myf(mynode9);
cout<<"after rotations :"<<endl;
print_tree(newroot);
return 0;
}
Do post order traversal and perform LL and RR rotation around each '*' node.
- Anonymous May 13, 2012