CareerCup

At every alternate level:
1. Put the nodes in an array
2. Reverse the array
3. Put the nodes back in the tree at that level.
Code for the same:

#include <stdio.h>
#include <conio.h>
#include <malloc.h>
typedef struct tree
{
	char data;
	tree *left,*right;
};
tree *newNode(char data)
{
	tree *n=(tree *)malloc(sizeof(tree));
	n->data=data;
	n->left=n->right=NULL;
	return n;
}
int calheight(tree *root)
{
	if(root==NULL)
		return 0;
	else
	{
		int l=calheight(root->left);
		int r=calheight(root->right);
		if(l>r)
			return (l+1);
		else
			return (r+1);	
	}	
}
void reverse(char arr[],int length)
{
	int i=0,j=length-1;
	while(i<j)
	{
		char temp=arr[i];
		arr[i++]=arr[j];
		arr[j--]=temp;
	}
}
void printLevel(tree *root,int level)
{
	if(root==NULL)
		return;
	if(level==1)
		printf(" %c ",root->data);
	else if(level>1)
	{
		printLevel(root->left,level-1);
		printLevel(root->right,level-1);
	}		
}
void changeLevel(tree **root,int level,char arr[],int *index,int flag)
{
	if(root==NULL)
		return;
	if(level==1)
	{
		if(flag==1)
			arr[(*index)++]=(*root)->data;	
		else
			(*root)->data=arr[(*index)++];	
	}
	else if(level>1)
	{
		changeLevel(&((*root)->left),level-1,arr,index,flag);
		changeLevel(&((*root)->right),level-1,arr,index,flag);
			
	}		
}
void changeLevelOrder(tree *root)
{
	int height=calheight(root),j=0;
	char arr[100];
	for(int i=0;i<=height;i=i+2)
	{
		changeLevel(&root,i,arr,&j,1);
		reverse(arr,j);	
		j=0;	
		changeLevel(&root,i,arr,&j,0);
		j=0;
	}
	for(int i=1;i<=height;i++)
	{
		printLevel(root,i);
	}
}
int main()
{
	tree *root=newNode('a');
	root->left        = newNode('b');
	root->right       = newNode('c');
	root->left->left  = newNode('d');
	root->left->right = newNode('e');
	root->right->left = newNode('f');
	root->right->right = newNode('g');
	root->left->left->left = newNode('h');
	root->left->left->right = newNode('i');
	root->left->right->left = newNode('j');
	root->left->right->right = newNode('k');
	root->right->left->left = newNode('l');
	root->right->left->right = newNode('m');
	root->right->right->left = newNode('n');
	root->right->right->right = newNode('o');
  	changeLevelOrder(root);
  
}

#include<bits/stdc++.h>
int main()
{
	char arr[50];
	sfs(arr+1);
	puts(arr+1);int count=1;
	for(int i=1,j=1;arr[j]!='\0';){
		int start=i*2,end=j*2+1;
		if(count%2)
		for(;end>start;start++,end--){
			int temp=arr[end];
			arr[end]=arr[start];
			arr[start]=temp;
		}
		count++;
		i=i*2;j=j*2+1;
	}
	puts(arr+1);
	return 0;
}

//sorry in previous code arr[j+1]!='\0' rather than arr[j]!='\0'
//we reversing at even levels
//inorder traversal can be used for printing the nodes in a better way rather than //straightway printing using puts(arr)

#include<bits/stdc++.h>
int main()
{
	char arr[200];
	sfs(arr+1);
	puts(arr+1);int count=1;
	for(int i=1,j=1;arr[j+1]!='\0';){
		int start=i*2,end=j*2+1;
		if(count%2)
		for(;end>start;start++,end--){
			int temp=arr[end];
			arr[end]=arr[start];
			arr[start]=temp;
		}
		count++;
		i=i*2;j=j*2+1;
	}
	puts(arr+1);
	return 0;
}

Just a zig-zag traverse?

it prints

package com.cnu.ds.tree;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

public class Tree {
	public static void main(String[] args) {
		TreeNode treeNode = new TreeNode();
		treeNode.t = 1;
		treeNode.left = new TreeNode();
		treeNode.left.t = 2;
		treeNode.right = new TreeNode();
		treeNode.right.t = 3;
		treeNode.left.left = new TreeNode();
		treeNode.left.left.t = 4;
		treeNode.left.right = new TreeNode();
		treeNode.left.right.t = 5;
		treeNode.right.left = new TreeNode();
		treeNode.right.left.t = 6;
		treeNode.right.right = new TreeNode();
		treeNode.right.right.t = 7;
		levelOrder(treeNode);
	}

	public static void levelOrder(TreeNode root) {
		Queue<TreeNode> treeNodes = new LinkedList<>();
		treeNodes.add(root);
		treeNodes.add(null);
		Stack<TreeNode> stack = new Stack<>();
		boolean flip = true;
		while (!treeNodes.isEmpty()) {
			root = treeNodes.remove();
			if (root == null) {
				if (flip) {
					while (!stack.isEmpty()) {
						System.out.print(stack.pop().t + " ");
					}
				}
				flip = !flip;
				if (treeNodes.isEmpty()) {
					break;
				}
				System.out.println();
				treeNodes.add(null);
			} else {
				if (root.left != null) {
					treeNodes.add(root.left);
				}
				if (null != root.right) {
					treeNodes.add(root.right);
				}
				if (flip) {
					stack.push(root);
				} else {
					System.out.print(root.t + " ");
				}
			}
		}
	}
}

package com.cnu.ds.tree;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

public class Tree {
	public static void main(String[] args) {
		TreeNode treeNode = new TreeNode();
		treeNode.t = 1;
		treeNode.left = new TreeNode();
		treeNode.left.t = 2;
		treeNode.right = new TreeNode();
		treeNode.right.t = 3;
		treeNode.left.left = new TreeNode();
		treeNode.left.left.t = 4;
		treeNode.left.right = new TreeNode();
		treeNode.left.right.t = 5;
		treeNode.right.left = new TreeNode();
		treeNode.right.left.t = 6;
		treeNode.right.right = new TreeNode();
		treeNode.right.right.t = 7;
		// //////////////////////
		treeNode.left.left.left = new TreeNode();
		treeNode.left.left.left.t = 8;
		treeNode.left.left.right = new TreeNode();
		treeNode.left.left.right.t = 9;

		treeNode.left.right.left = new TreeNode();
		treeNode.left.right.left.t = 10;

		treeNode.left.right.right = new TreeNode();
		treeNode.left.right.right.t = 11;

		treeNode.right.left.left = new TreeNode();
		treeNode.right.left.left.t = 12;
		treeNode.right.left.right = new TreeNode();
		treeNode.right.left.right.t = 13;

		treeNode.right.right.left = new TreeNode();
		treeNode.right.right.left.t = 14;

		treeNode.right.right.right = new TreeNode();
		treeNode.right.right.right.t = 15;

		levelOrder(treeNode);
		levelOrderReverse(treeNode);
	}

	public static void levelOrderReverse(TreeNode root) {
		Queue<TreeNode> treeNodes = new LinkedList<>();
		TreeNode newRoot = root;
		treeNodes.add(root);
		treeNodes.add(null);
		Stack<Integer> stack = new Stack<>();
		Queue<TreeNode> queue = new LinkedList<>();
		boolean flip = false;
		while (!treeNodes.isEmpty()) {
			root = treeNodes.remove();
			if (root == null) {
				if (flip) {
					while (!queue.isEmpty()) {
						root = queue.remove();
						int r = stack.pop();
						int l = stack.pop();
						root.left.t = r;
						root.right.t = l;
					}
				}
				flip = !flip;
				if (treeNodes.isEmpty()) {
					break;
				}
				System.out.println();
				treeNodes.add(null);
			} else {
				if (root.left != null) {
					treeNodes.add(root.left);
				}
				if (null != root.right) {
					treeNodes.add(root.right);
				}
				if (flip) {
					stack.push(root.t);
				} else {
					queue.add(root);
				}
			}
		}
		System.out.println();
		levelOrder(newRoot);
	}

	public static void levelOrder(TreeNode root) {
		Queue<TreeNode> treeNodes = new LinkedList<>();
		treeNodes.add(root);
		treeNodes.add(null);
		Queue<TreeNode> queue = new LinkedList<>();
		while (!treeNodes.isEmpty()) {
			root = treeNodes.remove();
			if (root == null) {
				if (treeNodes.isEmpty()) {
					break;
				}
				System.out.println();
				treeNodes.add(null);
			} else {
				if (root.left != null) {
					treeNodes.add(root.left);
				}
				if (null != root.right) {
					treeNodes.add(root.right);
				}
				queue.add(root);
				System.out.print(root.t + " ");
			}
		}
	}
}

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



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

Let me know if I am correct or wrong
Thanks,
Srinivas.

I think if it's not forbidden, we can simply change data in tree nodes, traverse at first left and right nodes, then swap them.
i.e. in order traverse for left node and in order traverse for right node recursively.
Complexity is O(n).

public class TreeNode
{
    public TreeNode Left;
    public TreeNode Right;
    public string Data;
}

public static void ReverseNodes(TreeNode root)
{
    ReverseNodesInternal(root.Left, root.Right);
}

private static void ReverseNodesInternal(TreeNode left, TreeNode right)
{
    if (left == null || right == null)
        return;

    ReverseNodesInternal(left.Left, right.Right);
    ReverseNodesInternal(left.Right, right.Left);

    var tmp = left.Data;
    left.Data = right.Data;
    right.Data = tmp;
}

are we suppose to change links or just swapping the data would be enough?

Th above problem can be solved using 2 queues and a stack.
Let the two queues be q1 and q2 and the stack be s.

Initialize a variable flag hat determines the order for each level with 0
Firstly put the root in q1

Now do as follows :
For each level i
1) Dequeue from q1 and push its left and right child into the stack s. Also enqueue this dequeued item into q2

2)Now once you are done with pushing all the children for this level, pop two items from stack for a single dequeued item from q2 var_q2. Now you have two items from stack that will become children of dequeued item from q2

if(flag == 1){
// for this level
// first set right child of q2_var
// then set left child of q2_var
// finally put left child and then right child of q2_var back to q1
// flag = 0;
}
else {
// for this level
// first set left child of q2_var
// then set right child of q2_var
// finally put left child and then right child of q2_var back to q1
// flag = 0;
}
// Repeat this procedure until q1 is Empty

Here is a working code for the above problem

#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <queue>
#include <stack>
using namespace std;
struct BTreeNode{
    char ch;
   struct BTreeNode *left;
    struct BTreeNode *right;
}BTreeNode;
struct BTreeNode * buildTree(){
    struct BTreeNode *root;
    root = new struct BTreeNode;
    root->left = root->right = NULL;
    root->ch = 'a';
    
    root->left = new struct BTreeNode;
    root->left->ch = 'b';
    root->right = new struct BTreeNode;
    root->right->ch = 'c';
    
    root->left->left = new struct BTreeNode;
    root->left->left->ch = 'd';
    root->left->right = new struct BTreeNode;
    root->left->right->ch = 'e';
    
    root->right->left = new struct BTreeNode;
    root->right->left->ch = 'f';
    root->right->right = new struct BTreeNode;
    root->right->right->ch = 'g';
    
    root->left->left->left = new struct BTreeNode;
    root->left->left->left->ch = 'h';
    root->left->left->right = new struct BTreeNode;
    root->left->left->right->ch = 'i';
    
    root->left->right->left = new struct BTreeNode;
    root->left->right->left->ch = 'j';
    root->left->right->right = new struct BTreeNode;
    root->left->right->right->ch = 'k';
    
    root->right->left->left = new struct BTreeNode;
    root->right->left->left->ch = 'l';
    root->right->left->right = new struct BTreeNode;
    root->right->left->right->ch = 'm';
    
    root->right->right->left = new struct BTreeNode;
    root->right->right->left->ch = 'n';
    root->right->right->right = new struct BTreeNode;
    root->right->right->right->ch = 'o';
    
    return root;
}
void level_order(struct BTreeNode *root){
 
    queue<struct BTreeNode *> q;
    struct BTreeNode *temp;
    q.push(root);
    q.push(NULL);
    while(!q.empty()){
        
        temp = q.front(); q.pop();
        
        if(q.empty()) break;
        if(temp == NULL) {cout<<"\n"; q.push(NULL); }
        else{
            cout<<temp->ch<<" ";
            if(temp->left)
                q.push(temp->left);
            if(temp->right)
                q.push(temp->right);
        }
    }
    cout<<"\n";
    
}
void alternate_nodes(struct BTreeNode *root){
    
    int flag = 0;
    struct BTreeNode *temp;
    stack<struct BTreeNode *> s;
    queue<struct BTreeNode *> q1,q2;
    q1.push(root);
    while(1){
        if(q1.empty()) break;
        while(!q1.empty()){
        q2.push(q1.front());
        temp = q1.front(); q1.pop();
            if(temp->left) s.push(temp->left);
            if(temp->right) s.push(temp->right);
            
        }
       
        
        if(flag == 1){
            
            while(!q2.empty()){
                 if(s.empty()) break;
                
                temp = q2.front(); q2.pop();   
                temp->right = s.top(); s.pop();
                if(s.empty()) break;
                temp->left = s.top(); s.pop();
             if(temp->left)   q1.push(temp->left);
                if(temp->right) q1.push(temp->right);
            }
            flag  = 0;
        }
        
        else{
            while(!q2.empty()){
                if(s.empty()) break;
                
                temp = q2.front(); q2.pop();
                temp->left = s.top(); s.pop();
                if(s.empty()) break;
                temp->right = s.top(); s.pop();
                if(temp->left)   q1.push(temp->left);
                if(temp->right) q1.push(temp->right);
            }
            flag = 1;
        }
        
        
    }
    level_order(root);
    
}
int main()
{
    struct BTreeNode *root;
    root = buildTree();
    
    level_order(root);
    alternate_nodes(root);
    
    return 0;
}

A solution with 2 in order traversals and one array:
1) Do an in order traversal of the tree and store all data at odd levels in the array (storealt)
2) reverse this array
3) Do in order traversal again - this time replacing the data at odd levels with the reversed data in the array (modifytree)

void storealt (node* root, int arr[], int *index,int level) {
   if root==NULL return;
   storealt(root->left,arr,index,level+1);
  if (level%2 == 0) {
    arr[*index] = root->data;
    *index++;
  }
storealt(root->right,arr,index,level+1);
}

Assumption:
1. Assuming that the tree is a complete binary tree following recursive function should work fine.

I have not run the code. Its just the algorithm which should work fine.

void
reverseAtAlternateLevel(node * tree, int level) {
	if ( tree->left == NULL && tree->right == NULL) {
		return;
	}
	if( level %2 == 0) {
		int temp = tree->left->data;
		tree->left->data = tree->right->data;
		tree->right->data = temp;
        }
	reverseAtAlternateLevel(tree->left, level++);
	reverseAtAlternateLevel(tree->right, level++);	
}

public Node MirrorAlternateLevelInTree(Node root) {
Node marker = new Node(-1);
if (root == null)
return null;
if (root.mRight == null && root.mLeft == null)
return null;

Queue<Node> queue = new LinkedList<Node>();
queue.add(root);
queue.add(marker);
List<Node> list = new ArrayList<Node>();
boolean flipFlag = true;
while (queue.peek() != null) {
Node node = queue.remove();
if (node.mRight != null) {
queue.add(node.mRight);
}
if (node.mLeft != null) {
queue.add(node.mLeft);
}
if (node == marker) {
if (flipFlag) {
list.addAll(queue);
reverseNodes(list);
flipFlag = false;
} else {
flipFlag = true;
}
list.clear();
if( !queue.isEmpty()){
queue.add(marker);
}

}
}
return root;
}

private void reverseNodes(List<Node> list) {
for (int i = 0; i < (list.size()/2); i++) {
int temp = list.get(i).mObject;
list.get(i).mObject = list.get(list.size() - 1 - i).mObject;
list.get(list.size() - 1 - i).mObject = temp;
}
}

Here's the solution using queue.

public Node MirrorAlternateLevelInTree(Node root) {
		Node marker = new Node(-1);
		if (root == null)
			return null;
		if (root.mRight == null && root.mLeft == null)
			return null;

		Queue<Node> queue = new LinkedList<Node>();
		queue.add(root);
		queue.add(marker);
		List<Node> list = new ArrayList<Node>();
		boolean flipFlag = true;
		while (queue.peek() != null) {
			Node node = queue.remove();
			if (node.mRight != null) {
				queue.add(node.mRight);
			} 
			if (node.mLeft != null) {
				queue.add(node.mLeft);
			}
			if (node == marker) {
				if (flipFlag) {
					list.addAll(queue);
					reverseNodes(list);
					flipFlag = false;
				} else {
					flipFlag = true;
				}
				list.clear();
				if( !queue.isEmpty()){
					queue.add(marker);
				}
				
			} 
		}
		return root;
	}

	private void reverseNodes(List<Node> list) {
		for (int i = 0; i < (list.size()/2); i++) {
			int temp = list.get(i).mObject;
			list.get(i).mObject = list.get(list.size() - 1 - i).mObject;
			list.get(list.size() - 1 - i).mObject = temp;
		}
	}

Here is a solution using recursion:

public class BinaryTree{

	//Class representing the Tree Node
	private static TreeNode{
		TreeNode left;
		TreeNode right;
		String data;

		public TreeNode(String data){
			left=right=null;
			this.data=data;
		}
	}

	private TreeNode root;

	public boolean isLeaf(Node node){
		return (node.left==null && node.right==null);
	}
	
	public void alternateReverse(){
		alternateReverse(root,true);
	}
	
	private void alternateReverse(TreeNode node,boolean doReverse){
		if(isLeaf(node))return;
		if(doReverse) reverse(node);
		
		doReverse= !doReverse;
		alternateReverse(node.left, reverse);
		alternateReverse(node.right, reverse);
	}
	
	private void reverse(Node node){
		int tmp=node.left.data;
		node.left.data=node.right.data;
		node.right.data=tmp;
	} 

}

hi Srinivas,

Simple stack and queue should work i guess, do we really need anything extra?

please correct the below steps if anything wrong:
1. add root to queue
2. flip variable is initially true, means push to stack left to right order
pop from queue and add to stack left, right nodes and push back to queue again
do this until queue size, here just 1 root is there in queue
3. now remove from queue and add as just normal left and right nodes taken from stack, here it sets now this way
a
c b

4. now push back to queue, a's left and right normlly, flip is set to false now
5. now for the first element c, its right and then left are pushed to stack until queue size is empy and push back again
stack is like
d
e
f
g
take out 2 elements each time and set as normal left and right subtrees for each element of queue and push back again, left and right elements of each newly set item to queue for later processing......

it is working this way.... please correct....

thank you

void reverseLevel(struct tree *root)
{
if(!root)return;

struct tree *q[30],*temp;
int rear=-1,front=-1;
int t,r,f,i=1;

q[++rear]=root;
q[++rear]=NULL;

while(front!=rear)
{
temp=q[++front];

if(temp==NULL)
{
if(i==1)
{
r=rear;
f=front+1;
while(f<r)
{
t=q[f]->data;
q[f]->data=q[r]->data;
q[r]->data=t;
f++;
r--;
}
}
temp=q[++front];

q[++rear]=NULL;

i=1-i;
}
if(temp->left)
q[++rear]=temp->left;
if(temp->right)
q[++rear]=temp->right;
}
}