Reverse Alternate levels of a given Binary Tree.

Objective: – Reverse Alternate levels of a given binary tree

Input: A binary tree

Example:

Reverse Alternate levels of a given binary tree.

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:

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

view raw

ReverseAlternateLevelsOfBinaryTree.java

hosted with ❤ by GitHub

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

Reverse Alternate levels of a given Binary Tree.

Related Posts:

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

Leave a Comment Cancel reply