CareerCup

Do post order traversal and perform LL and RR rotation around each '*' node.

Inorder traversal of the wrong tree will give us back the infix expression, convert that to a post fix expression using the correct operator precedence, and then parse the postfix expression to get the correct tree.

I hate that evil dwarf

Sounds like homework/programming puzzle.

This comment has been deleted.

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

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;
}

This tree is just an example..wat if we have any other tree..will this method work??