CareerCup

This can be solved with 2 stacks.
1. Read the root node and add it to the stack "even".
2. pop nodes out of the stack even. Now, read the right child first and then left, print it and push it to stack "odd". Do this until the stack even is empty.
3. Now, pop nodes out of stack odd. Read the left child first and then right, print it and push it to stack "even". Do this until the stack odd is empty.
4. repeat 2 and 3 until it was an empty stack to begin with - this means that we traversed the last level in the previous step

I guess this requires printing the tree in spiral form.

1. Start with root.
2. Since root is at odd level (and next level will be even), add its children in reverse order to the queue, i.e. root.right and then root.left
3. Proceed similarly for other levels.

If we are adding children of a particular node, following rule should be considered
a. if node at even level, add node.left then node.right
b. if node at odd level, add node.right then node.left

static void print(Node root)
{
Stack<Node> odd = new Stack<Node>();
Stack<Node> even = new Stack<Node>();
odd.Push(root);
while (odd.Count != 0 || even.Count != 0)
{
while (odd.Count != 0)
{
Node node = odd.Pop();
if(node.left!=null)
even.Push(node.left);
if(node.right!=null)
even.Push(node.right);
Console.Write(node.data+" ");
}
Console.WriteLine();
while (even.Count != 0)
{
Node node = even.Pop();
if (node.right != null)
odd.Push(node.right);
if (node.left != null)
odd.Push(node.left);
Console.Write(node.data + " ");
}
Console.WriteLine();
}
}

Here is my solution in C#, using two lists.

public static void PrintEvenOdd(TNode root)
        {
            bool isOdd = false;
            List<TNode> prevNodes = new List<TNode>();
            prevNodes.Add(root);
            PrintNodes(prevNodes);
            List<TNode> currNodes = new List<TNode>();

            while (prevNodes.Count > 0)
            {
                isOdd = !isOdd;
                currNodes.Clear();

                foreach (TNode node in prevNodes)
                {
                    if (node.left != null)
                        currNodes.Add(node.left);

                    if (node.right != null)
                        currNodes.Add(node.right);
                }
                if (isOdd)
                    currNodes.Reverse();
                PrintNodes(currNodes);
                prevNodes.Clear();
                if (isOdd)
                    currNodes.Reverse();
                prevNodes.AddRange(currNodes);

            }
        }
        
        private static void PrintNodes(List<TNode> list)
        {
            foreach (TNode node in list)
            {
                Console.Write(node.data + " ");
            }
            Console.WriteLine();
        }

but wouldn't that print 'a c b f g d e'

I think a Broad First Search with a stack can solve this problem.
1. Add the root node to the queue.
2. Get the head node of the queue and add its children to the queue.
3. If the node is in even level, print it. Otherwise, push it into the stack
4. When level of the head node has changed from odd to even,pop the stack and print the node
5. Repeat from 2 until all the node have been scaned

another solution to this is to use "deque"

1. odd levels - print the node value from the bottom and push the child nodes to the top

2. even levels - print the node value from the top end and push the child nodes to the bottom

always pop the node after printing its value

also we will have a couple of O(1) memory - one to track the number of elements to print during the current print option and other one is for the number of elements in the next level.

Please correct me if I am wrong

vector< vector<tree *> > v;
  vector<tree *>x;
  x.push_back(root);
  v.push_back(x);
  int i=0;
  while(!v[i].empty())
  {
   x.clear();
   if(i%2==0)
   {
    for(int j=v[i].size()-1;j>=0;j--)
    {
     if(v[i][j]->left) x.push_back(v[i][j]->left);
     if(v[i][j]->right) x.push_back(v[i][j]->right);
     cout<<v[i][j]->info<<" ";
    }
   }
    if(i%2!=0)
   {
    for(int j=v[i].size()-1;j>=0;j--)
    {
     if(v[i][j]->right) x.push_back(v[i][j]->right);
     if(v[i][j]->left) x.push_back(v[i][j]->left);
     cout<<v[i][j]->info<<" ";
    }
   }
   v.push_back(x);
    i++;
   }

vector<node*> print_odd_level(vector<node*> nodes) {
  for (int i=0; i<nodes.size(); i++) 
    cout << nodes[i]->value << " ";
  return next_level(nodes);
}
vector<node*> print_even_level(vector<node*> nodes) {
  for (int i=nodes.size()-1; i>=0; i--)
    cout << nodes[i] << " ";
  return next_level(nodes);
}
vector<node*> next_level(vector<node*> nodes) {
  vector<node*> next;
  for (int i=0; i<nodes.size(); i++) {
    if (nodes[i]->left)
      next.push_back(nodes[i]->left);
    if (nodes[i]->right)
      next.push_back(nodes[i]->right);
  }
  return next;
}

void print() {
  if (!root) return;
  vector<node*> nodes;
  nodes.push_back(root);
  int level = 1;
  while (!nodes.empty()) {
    if (level%2==1) 
      nodes = print_odd_level(nodes);
    else
      nodes = print_even_level(nodes);
  }
}

Ans to Ques 1 :
Do a level order traversal using a queue.
Pseudocode

Enqueue(Q, root)
Enqueue(Q, NULL) //marker for level end
while (!isEmptyQueue(Q)) {
           temp = Dequeue(Q);
           if (temp == NULL) {
               //marks end of level
               //Pop all the elements and print
               if (!isEmptyQueue(Q))
                   Enqueue(Q, NULL) //marker
           }
           Push(stack, temp);
           if (temp->left)
               Enqueue(Q, temp->left);
           if (temp->right)
               Enqueue(Q, temp->right);
}

The other question can be solved as well by making minor modifications

Code for Reverse Level Order for each Level procedure

#include <iostream>
#include <stack>
#include <queue>
using namespace std;

void ReverseLevelOrderForEachLevel(struct Node *root) {
	struct Node *temp;
	if(!root)
		return;
	queue<Node*> Q;
	stack<Node*> S;
	Q.push(root);
	Q.push(NULL);
	while (!Q.empty()) {
		temp = Q.front();
		Q.pop();
		if (temp == NULL) {
			while(!S.empty()) {
				cout<<S.top()->data<<" ";
				S.pop();
			}
			cout<<endl;
			if(!Q.empty()) {
				Q.push(NULL);
			}
		}
		else {
			S.push(temp);
			if(temp->left)
				Q.push(temp->left);
			if(temp->right)
				Q.push(temp->right);
		}
	}
}

public NodeQueue bfs(Node traverseNode, int level) {
		NodeQueue nodeQueue = new NodeQueue();
		NodeQueue resultQueue = new NodeQueue();
		traverseNode.setLevel(1);
		nodeQueue.push(traverseNode);
		resultQueue.push(traverseNode);
         
		while (!nodeQueue.isEmpty()) {
			 
			traverseNode = nodeQueue.pop();
			level = traverseNode.getLevel();
			level++;
			if (traverseNode.getLeft() != null) {
				traverseNode.getLeft().setLevel(level);
				nodeQueue.push(traverseNode.getLeft());
			//	resultQueue.push(traverseNode.getLeft());
			}
			if (traverseNode.getRight() != null) {
				traverseNode.getRight().setLevel(level);
				nodeQueue.push(traverseNode.getRight());
			//	resultQueue.push(traverseNode.getRight());
			}
			
			if(level%2==0){
				if (traverseNode.getRight() != null) {
					resultQueue.push(traverseNode.getRight());
				}
				if (traverseNode.getLeft() != null) {
					resultQueue.push(traverseNode.getLeft());
				}
			}
			else
			{
				if (traverseNode.getLeft() != null) {
					resultQueue.push(traverseNode.getLeft());
				}
				if (traverseNode.getRight() != null) {
					resultQueue.push(traverseNode.getRight());
				}
			}
			
		}
		return resultQueue;
	}

void LevelOrderTraval(BST *Node)
{
std::queue<BST*> QueueToHold;
QueueToHold.push(Node);

while(!QueueToHold.empty())
{
BST *tmp = QueueToHold.front();
QueueToHold.pop();
std::cout<< tmp->data <<"\n";

if (tmp->lChild)
QueueToHold.push(tmp->lChild);
if (tmp->rChild)
QueueToHold.push(tmp->rChild);
}

1. do an pre-oder and print values in an array also label then with their levels

a bdecfg
1233233

now just read appropiately

odd from tight and even from level .. level wise

How about this?

public class OddEvenTreeTraversal {
	private static void printTree(TreeNode root){
		Stack<TreeNode> oddStack = new Stack<TreeNode>();
		Stack<TreeNode> evenStack = new Stack<TreeNode>();
		oddStack.push(root);
		while(!oddStack.empty() || !evenStack.empty()){
			while(!oddStack.empty()){
				TreeNode n = oddStack.pop();
				System.out.println(n.data);
				if(n.left!=null)
				evenStack.push(n.left);
				if(n.right!=null)
				evenStack.push(n.right);
			}
			while(!evenStack.empty()){
				TreeNode n = evenStack.pop();
				System.out.println(n.data);
				if(n.right!=null)
				oddStack.push(n.right);
				if(n.left!=null)
				oddStack.push(n.left);
			}
		}
	}
	
	public static void main(String[] argv){
		TreeNode d = new TreeNode('d');
		TreeNode e = new TreeNode('e');
		TreeNode f = new TreeNode('f');
		TreeNode g = new TreeNode('g');
		TreeNode c = new TreeNode('c');
		TreeNode b = new TreeNode('b');
		TreeNode a = new TreeNode('a');
		a.left = b;
		a.right = c;
		b.left = d;
		b.right= e;
		c.left = f;
		c.right = g;
		printTree(a);
	}
	

}

class TreeNode{
	char data;
	TreeNode left;
	TreeNode right;
	public TreeNode(char data){
		this.data = data;
	}
}

queue q = new queue();
q.add(root)
stack s = new stack();
while((isOdd && !q.empty())||(!isOdd && !s.empty())
{
if(isOdd)
{
whie(!q.isempty){Node n =e.dequeue; print(n);s.push(n.left);s.push(n.right);isodd=false;}
}
else
{
while(!s.empty){Node n = s.pop;print n;enque(n.left);n.enque(n.right);}
}
}

It reverses order of all the nodes of tree after level 1.

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.Queue;

public class BSTPrint {
	TreeNode root;

	class TreeNode {
		double value;
		TreeNode left;
		TreeNode right;

		public TreeNode(double value) {
			super();
			this.value = value;
			left = null;
			right = null;
		};

	}

	public void insert(double value) {
		root = insertT(root, value);
	}

	public TreeNode insertT(TreeNode root, double value) {
		if (root == null) {
			TreeNode r = new TreeNode(value);
			return r;
		}
		if (value > root.value) {
			// right
			root.right = insertT(root.right, value);
		} else if (value < root.value) {
			root.left = insertT(root.left, value);
		}
		return root;
	}

	public void inorder() {
		inorderT(root);
		System.out.println();
	}

	private void inorderT(TreeNode root) {
		if (root == null) {
			return;
		}
		inorderT(root.left);
		System.out.print(root.value + "\t");
		inorderT(root.right);
	}

	/**
	 * WAP to print the node values of a binary tree - Even level starting from
	 * right to left - Odd level starting from left to right Assume that level
	 * of root is 1.
	 */
	public void levelPrint() {
		if (root == null) {
			return;
		}
		Deque<TreeNode> deque = new ArrayDeque<TreeNode>();
		deque.offerLast(root);
		int level = 1;
		while (!deque.isEmpty()) {
			if (level % 2 == 1) {
				for (Iterator<TreeNode> iterator = deque.iterator(); iterator
						.hasNext();) {
					System.out.print(iterator.next().value + " ");
				}
			} else {
				for (Iterator<TreeNode> iterator = deque.descendingIterator(); iterator
						.hasNext();) {
					System.out.print(iterator.next().value + " ");
				}
			}
			int size = deque.size();
			while (size > 0) {
				TreeNode node = deque.pollFirst();
				if (node.left != null)
					deque.addLast(node.left);
				if (node.right != null)
					deque.addLast(node.right);
				size--;
			}
			level++;
		}
	}

	public static void main(String[] args) {
		BSTPrint bst = new BSTPrint();
		bst.insert(6);
		bst.insert(5);
		bst.insert(4);
		bst.insert(2);
		bst.insert(8);
		bst.insert(7);
		bst.insert(3);
		bst.insert(9);
		bst.levelPrint();
	}

}

Build a mapping between level and nodes: Do a BFS traverse, store following in a hashtable: key: level , value: list of nodes in level

do a foreach on hashtable print nodes for each level from first to last (or last to first) regarding odd (even) level.

Complexity: O(n)