> For the complete documentation index, see [llms.txt](https://mayanktyagi3111.gitbook.io/interview-prep/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://mayanktyagi3111.gitbook.io/interview-prep/trees/reverse-alternate-levels-of-a-perfect-binary-tree.md).

# Reverse alternate levels of a perfect binary tree

Given a [Perfect Binary Tree](http://en.wikipedia.org/wiki/Binary_tree#Types_of_binary_trees), 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 
```

```java
class Tree {
    static void reverseAlternate(Node root) {
        if (root == null)
            return;
        Queue<Node> q = new LinkedList<>();
        q.add(root);
        ArrayList<Node> level1 = new ArrayList<>();
        boolean rotate = false;
        while (q.size() != 0) {
            int size = q.size();
            ArrayList<Node> level2 = new ArrayList<>();
            while (size-- > 0) {
                Node temp = q.poll();
                level2.add(temp);
                if (temp.left != null)
                    q.add(temp.left);
                if (temp.right != null)
                    q.add(temp.right);
            }
            if (level1.size() > 0) {
                if (rotate)
                    Collections.reverse(level2);
                for (int i = 0; i < level1.size(); i++) {
                    level1.get(i).left = level2.get(2 * i);
                    level1.get(i).right = level2.get(2 * i + 1);
                }
            }
            rotate = !rotate;
            level1 = level2;
        }
    }
}
```