Reverse alternate levels of a perfect binary tree | GeeksforGeeks
Given a Perfect Binary Tree, reverse the alternate level nodes of the binary tree.
http://algorithms.tutorialhorizon.com/reverse-alternate-levels-of-a-given-binary-tree/
https://learn.hackerearth.com/tutorial/trees/105/reverse-alternate-levels-of-a-fullperfect-binary-t/
Given a Perfect Binary Tree, reverse the alternate level nodes of the binary tree.
Given tree:
a
/ \
b c
/ \ / \
d e f g
/ \ / \ / \ / \
h i j k l m n o
Modified tree:
a
/ \
c b
/ \ / \
d e f g
/ \ / \ / \ / \
o n m l k j i h
A perfect binary tree is a full binary tree in which all leaves have the same depth or same level.
A simple solution is to do following steps.
1) Access nodes level by level.
2) If current level is odd, then store nodes of this level in an array.
3) Reverse the array and store elements back in tree.
1) Access nodes level by level.
2) If current level is odd, then store nodes of this level in an array.
3) Reverse the array and store elements back in tree.
A tricky solution is to do two inorder traversals. Following are steps to be followed.
1) Traverse the given tree in inorder fashion and store all odd level nodes in an auxiliary array. For the above example given tree, contents of array become {h, i, b, j, k, l, m, c, n, o}
1) Traverse the given tree in inorder fashion and store all odd level nodes in an auxiliary array. For the above example given tree, contents of array become {h, i, b, j, k, l, m, c, n, o}
2) Reverse the array. The array now becomes {o, n, c, m, l, k, j, b, i, h}
3) Traverse the tree again inorder fashion. While traversing the tree, one by one take elements from array and store elements from array to every odd level traversed node.
public static ArrayList al; public void storeAlterNateLevels(Node root,int level){ if(root!=null){ storeAlterNateLevels(root.left,level+1); if(level%2!=0){ al.add(root.data); } storeAlterNateLevels(root.right,level+1); } } public void reverseAlterNateLevels(Node root,int level){ if(root!=null){ reverseAlterNateLevels(root.left,level+1); if(level%2!=0){ root.data = (Integer)al.remove(0); } reverseAlterNateLevels(root.right,level+1); } } i.storeAlterNateLevels(root,0); Collections.reverse(al); i.reverseAlterNateLevels(root,0); 1.Do level order traversal.Following are steps to be followed.
2.Initially take a variable level and initialize with 1.
3.Push root and NULL in a queue, root's left and right child in a stack.
4.Now iterate over a loop while queue is not empty:
4.a Pop element from queue and store in a temp variable.
4.a.1 If poped element is NULL and queue is not empty,it
indicates that and of level and we will push a NULL.
4.b if level is odd :
4.b.1 Poped stack's top element and add to left of temp.
4.b.2 Poped one more element and add to right of temp.
4.b.3 Now we altered the reference so we have to arrange left
and right sub-tree of altered nodes.
Just replace left of Left subtree to left of right Subtree.
Replace right of Left subtree to right of Right subtree.
4.b.4 push temp's left and temp's right to the queue.
4.c if level is even :
4.c.1 Push temp->left's left and right child to the stack.
4.c.2 similarly for temp->right's children.
void alterNodes(struct node *root){
if(root == NULL)
return ;
queue<struct node*>q;
stack<struct node*>s;
int level = 1;
struct node *temp,*Left,*Right,*rev;
q.push(root);
q.push(NULL); //end of level
s.push(root->left);
s.push(root->right);
while(!q.empty())
{
temp = q.front();
q.pop();
if(temp == NULL)
{
if(!q.empty())
q.push(NULL);
level++;
}
else
{
if(level%2) //odd level
{
temp->left = s.top();
s.pop();
temp->right = s.top();
s.pop();
Left = temp->left;
Right = temp->right;
rev = Left->left; //adjust left subtree
Left->left = Right->left;
Right->left = rev;
rev = Left->right; //adjust right subtree
Left->right = Right->right;
Right->right = rev;
}
if(temp->left)
q.push(temp->left);
if(temp->right)
q.push(temp->right);
if(level%2==0) //even level
{
if(temp->left)
{
s.push(temp->left->left);
s.push(temp->left->right);
}
if(temp->right)
{
s.push(temp->right->left);
s.push(temp->right->right);
}
}
}
}
}
http://www.njiang.cn/2014/07/12/reverse-alternate-levels-of-a-perfect-binary-tree/void traverseNode(struct Node* root, int level, vector<vector<int> >& lists){if (root == NULL) {return;}if (lists.size() < level + 1) {lists.push_back(vector<int>());}lists[level].push_back(root->data);traverseNode(root->left, level+1, lists);traverseNode(root->right, level+1, lists);}void replaceNode(struct Node* root, int level, vector<vector<int> >& lists){if (root == NULL) {return;}if (lists[level].size() == 0) {return;}if (level%2 != 0) {size_t count = lists[level].size();root->data = lists[level][count - 1];lists[level].pop_back();}replaceNode(root->left, level+1, lists);replaceNode(root->right, level+1, lists);}
Read full article from Reverse alternate levels of a perfect binary tree | GeeksforGeeksvoid reverseTree(struct Node* root){if (root == NULL) {return;}vector<vector<int> > lists;traverseNode(root, 0, lists);replaceNode(root, 0, lists);}
