Reverse alternate levels of a perfect binary tree

Reverse alternate levels of a perfect binary tree

  September 09, 2017    

---

Idea is to either traverse tree and store data of every alternate Level in stack and again traverse tree and insert values from stack to every alternate Level

Code:

void store(Stack<Integer> s,Node node,boolean flag)
{
   if(node==null)
   return;
   store(s,node.left,!flag);
   if(flag)
   s.push(node.data);
   store(s,node.right,!flag);
}
void replace(Stack<Integer> s,Node node,boolean flag)
{
     if(node==null)
   return;
   replace(s,node.left,!flag);
   if(flag)
   node.data=s.pop();
   replace(s,node.right,!flag);
}
        void reverseAlternate(Node node)
        {
            Stack<Integer> s=new Stack<Integer>();
                store(s,node,false);
                replace(s,node,false);
        }

Idea 2 :

Traverse tree by passing left and right of subtree such that element of 1st left subtree will be replace by nth right subtree .


Code:

void swapValue(Node left,Node right)
{
    int l=left.data;
  left.data=right.data;
   right.data=l;
}
void reverse(Node l,Node r,boolean flag)
{
   if(l==null || r==null)
   return;
   if(flag)
   swapValue(l,r);
   reverse(l.left,r.right,!flag); // swap value of 1st left subtree with right most
   reverse(l.right,r.left,!flag); //swap value of right subtree with left most of another subtree
}
        void reverseAlternate(Node node)
        {
                reverse(node.left,node.right,true);
        }