# Reverse Alternate levels of a given Binary Tree.

Objective: Reverse Alternate levels of a given binary tree

Input: A binary tree

Example:

Appraoch:

• Do the inorder traversal and store all the alternate level nodes in an ArrayList.
• Reverse the ArrayList
• Do another inorder traversal and place the reversed array list in the same order in which it was fetched in step one.
• Look at the code for clear explanation.

Complete Code:

This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.

 import java.util.ArrayList; import java.util.Collections; import java.util.LinkedList; import java.util.Queue; public class ReverseAlternateLevelsOfBinaryTree { 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); } } public void levelOrderQueue(Node root){ Queue q = new LinkedList(); int levelNodes =0; if(root==null) return; q.add(root); while(!q.isEmpty()){ levelNodes = q.size(); while(levelNodes>0){ Node n = (Node)q.remove(); System.out.print("" + n.data); if(n.left!=null) q.add(n.left); if(n.right!=null) q.add(n.right); levelNodes—; } System.out.println(""); } } public void inorder(Node root){ if(root!=null){ inorder(root.left); System.out.print("" + root.data); inorder(root.right); } } public static void main (String[] args) throws java.lang.Exception { Node root = new Node(1); root.left = new Node (2); root.right = new Node (3); root.left.left = new Node (4); root.left.right = new Node (5); root.right.left = new Node (6); root.right.right = new Node (7); root.left.left.left = new Node (8); root.left.left.right = new Node (9); root.left.right.left = new Node (10); root.left.right.right = new Node (11); root.right.left.left = new Node (12); root.right.left.right = new Node (13); root.right.right.left = new Node (14); root.right.right.right = new Node (15); ReverseAlternateLevelsOfBinaryTree i = new ReverseAlternateLevelsOfBinaryTree(); al = new ArrayList(); System.out.println("Orininal Tree"); //i.inorder(root); i.levelOrderQueue(root); i.storeAlterNateLevels(root,0); // System.out.println("LIst " + al); Collections.reverse(al); i.reverseAlterNateLevels(root,0); System.out.println("\n New Tree, Alternate Levels Reversed.."); //i.inorder(root); i.levelOrderQueue(root); } } class Node{ int data; Node left; Node right; public Node (int data){ this.data = data; left = null; right = null; } }

Output:
Orininal Tree

1
2 3
4 5 6 7
8 9 10 11 12 13 14 15

New Tree, Alternate Levels Reversed..
1
3 2
4 5 6 7
15 14 13 12 11 10 9 8

### 1 thought on “Reverse Alternate levels of a given Binary Tree.”

1. solution given works only in case of perfect binary tree.