CareerCup

public static void printLevel(TreeNode root , int level,boolean ltr){

        if(root == null) return;
        if(level == 1) System.out.print(root.data+" ");


        else if(ltr == true)  {

            printLevel(root.left,level-1,ltr);
            printLevel(root.right, level - 1,ltr);
        }else {
            printLevel(root.right, level - 1,ltr);
            printLevel(root.left,level-1,ltr);

        }


    }


    public static void inwardSpiral(TreeNode root){

        int h = height(root);

        int firstLevel = 1;
        int lastLevel = h;

        while (firstLevel < lastLevel){


            printLevel(root, firstLevel, true);
            printLevel(root, lastLevel, false);
            firstLevel++;
            lastLevel--;
        }
 }

C#,

void PrintInwardSpiralTree(TreeNode root)
{
	if (root == null)
		return;

	var list = new List<List<TreeNode>>();
	var currentList = new List<TreeNode>();
	var nextList = new List<TreeNode>();
	currentList.Add(root);

	while (currentList.Count > 0)
	{
		list.Add(currentList);
		nextList = new List<TreeNode>();
		foreach (var node in currentList)
		{
			if (node.Left != null)
				nextList.Add(node.Left);
			if (node.Right != null)
				nextList.Add(node.Right);
		}
		currentList = nextList;
	}

	int n = list.Count;
	int first = 0;
	int last = n - 1;
	int i = 1;

	while (i <= n)
	{
		if (i % 2 == 1)
		{
			currentList = list[first];
			for (int j = 0; j < currentList.Count; j++)
				Console.Write(currentList[j].Value + ", ");
			first++;
		}
		else
		{
			currentList = list[last];
			for (int j = currentList.Count - 1; j >= 0;  j--)
				Console.Write(currentList[j].Value + ", ");
			last--;
		}

		i++;
	}

	Console.WriteLine();
}

BFS.
First scan tree and store all levels in some DS (or DSs) with marking the number of level.
Then using the DS, print all nodes according to the task.
The same is for n-ary tree: BFS eats all trees kinds :)
Quite straightforward.
Space O(n).
Is an O(1) space solution possible?

I propose a two step solution here:

1. Using a Depth First Traversal, push all the elements into a stack(S1) with a stub/delimiter in between each level. This can be achieved with a queue(Q) and stack(S1) as follows:

Push root element into the queue and then push a delimiter/stub value into the queue
While queue not empty:
  dequeue next element
  if(!delimiter)
	push element into stack S1
  enqueue its childern into the queue
  else //if delimiter
	push a delimiter into both stack and queue

2. Using two stacks S1 and S2, pop the levels in the spiral way i.e. pop top level from S1(level 1 of the tree), then pop remaining S1 into S2. Pop first level of S2(level n of binary tree) and pop remaining S2 into S1 and repeat till empty.

Minor variation of another answer already listed. In Java:

void printSpiral(Node root) {
	final int height = getHeight(root);

	int i;
	for (i = 0; i < (height / 2); i++) {
		printLevelLeftToRight(i + 1, 1, root);
		printLevelRightToLeft(height - i, 1, root);
	}
	if ((height % 2) == 1) {
		printLevelLeftToRight(i + 1, 1, root);
	}

	System.out.println();
}

void printLevelLeftToRight(final int desiredLevel, int currentLevel, final Node node) {
	if (desiredLevel == currentLevel) {
		System.out.print(node.data + " ");
		return;
	}

	if (node.left != null) {
		printLevelLeftToRight(desiredLevel, currentLevel + 1, node.left);
	}
	if (node.right != null) {
		printLevelLeftToRight(desiredLevel, currentLevel + 1, node.right);
	}
}

void printLevelRightToLeft(final int desiredLevel, int currentLevel, final Node node) {
	if (desiredLevel == currentLevel) {
		System.out.print(node.data + " ");
		return;
	}

	if (node.right != null) {
		printLevelRightToLeft(desiredLevel, currentLevel + 1, node.right);
	}
	if (node.left != null) {
		printLevelRightToLeft(desiredLevel, currentLevel + 1, node.left);
	}
}

FP implementation in Scala. It is lazily evaluated so it should consume very little memory.

1. transform tree into rows (BFS)
2. generate sequence for traversal and map to rows

case class BTree[+T](left: Option[BTree[T]], right: Option[BTree[T]], value: T)

object SpiralTraversal {
  def traverse[T](tree: BTree[T]): Iterator[T] = {
    type BT = BTree[T]

    def visit(nodes: Stream[BT]): (Stream[T], Stream[BT]) = {
      nodes.foldLeft((Stream.empty[T], Stream.empty[BT])) {
        case ((outT, outRow), node) =>
          val nextRow = Stream(node.left, node.right).flatMap {
            case Some(subtree) => Stream(subtree)
            case _ => Stream.empty
          }
          (outT ++ Stream(node.value), outRow ++ nextRow)
      }
    }

    def makeRows(trees: Stream[BT]): List[Stream[T]] = {
      if (trees.isEmpty) {
        return List.empty
      }
      val (rowT, nextRow) = visit(trees)
      List(rowT) ++ makeRows(nextRow)
    }

    def comb(n: Int, m: Int): Stream[(Int, Boolean)] =
      if (n > m) {
        Stream.empty
      } else if (n == m) {
        Stream((n, false))
      } else {
        (n, false) #::(m, true) #:: comb(n + 1, m - 1)
      }

    val rows = makeRows(Stream(tree))
    comb(0, rows.size - 1).flatMap {
      case (rowNumber, reversed) =>
        val row = rows(rowNumber)
        if (reversed) row.reverse else row
    }.iterator
  }
}

void inward(TreeNode* root){
	
	int count = 0;
	queue<TreeNode*> q;
	vector<vector<int> > result;
	
	if(root != NULL){
		count++;
		q.push(root);
	}
	
	while(count != 0){
		
		
		int newcount = 0;
		vector<int> level;
		
		for(int i = 0; i < count; ++i){
		
			TreeNode* curr = q.front();
			q.pop();
			
			level.push(curr->val);
			
			if(curr->left){
				newcount++;
				q.push(curr->left);
			}
			
			if(curr->right){
				newcount++;
				q.push(curr->right);
			}
		}
		
		result.push_back(level);
		count = newcount;		
	}
	
	int left = 0, right = result.size() - 1;
	
	while(left <= right){
	
		vector<int> level = result[left++];
		for(int i : level){
			cout << i << " ";
		}
		cout << endl;
			
		if(left < right){
			level = result[right--];
			
			for(int i = level.size() - 1; i >= 0; i--){
				cout << i << " ";
			}
			cout << endl;
		}
	}
	
}

Serialize the tree using BFS and use 2 indexes, from start and end

Using the HashMap and Dequeue as the DS

public void printSpiralInwards(Node root){
		
		Map<Integer,ArrayList<Node>> mp = new HashMap<Integer, ArrayList<Node>>();
		
		ArrayList<Node> arrayList = null;
		ArrayList<Node> arrayList1 = null;
		int i = 0;
		if(root == null)
			return;
		
		Deque<Node> queue = new LinkedList<Node>();
		queue.add(root);
		queue.add(null);
		while(queue.size()>1){
	   Node temp = queue.peekFirst();
	   
	   arrayList = new ArrayList<Node>();
	   while(temp!=null){
		  
		  temp = queue.pollFirst();
		  arrayList.add(temp);
		  System.out.println(" "+ temp.data );
		   
		    if(temp.left!=null)
			  	queue.offerLast(temp.left);
			  if(temp.right!=null)	  
				  queue.offerLast(temp.right);
			  temp = queue.peekFirst();
	   }
	   mp.put(i++, arrayList);
	   temp = queue.peekLast();
	   arrayList1 = new ArrayList<Node>();
	   while(temp!=null){
			  temp = queue.pollLast();
			  arrayList1.add(temp);
			  System.out.println(" "+ temp.data );
			  if(temp.right!=null)
				  	queue.offerFirst(temp.right);
				  if(temp.left!=null)	  
					  queue.offerFirst(temp.left);
				  temp = queue.peekLast();
		   }
	   			mp.put(i++, arrayList1);
		}
		
		
		   		   
		   Deque<ArrayList<Node>> de = new LinkedList<ArrayList<Node>>();
		   de.addAll(mp.values());

		   while(!de.isEmpty()){
		   System.out.println(" ");
		   ArrayList<Node> first = de.pollFirst();
		   Iterator<Node> itr = first.iterator();
		   while(itr.hasNext()){
			   System.out.print(" "+itr.next().data);
		   }
		   
		   System.out.println(" ");
		   ArrayList<Node> sec = de.pollLast();
		   Iterator<Node> itr1 = sec.iterator();
		   while(itr1.hasNext()){
			   System.out.print(" "+itr1.next().data);
		   }
		   
		   
		   
		   }
		   
		   
		
			
			}

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Stack;

public class SpiralTree {
	static int getHeight(Node root) {
		if (root == null) {
			return 0;
		}

		return 1 + Math.max(getHeight(root.getLeft()), getHeight(root.getRight()));
	}

	static void printSpiral(Node root) {
		if (root == null) {
			return;
		}

		List<Node> nodesList = Arrays.asList(root);
		Queue<List<Integer>> queue = new LinkedList<>();
		Stack<List<Integer>> stack = new Stack<>();

		populateStackNQueue(nodesList, queue, stack, 1, getHeight(root));

		while (true) {
			if (queue.isEmpty() && stack.isEmpty()) {
				break;
			}

			if (!queue.isEmpty()) {
				List<Integer> valuesList = queue.poll();
				for (Integer value : valuesList) {
					System.out.print(" " + value);
				}
			}

			if (!stack.isEmpty()) {
				List<Integer> valuesList = stack.pop();

				for (int i = valuesList.size()-1; i >= 0; i--) {
					System.out.print(" " + valuesList.get(i));
				}
			}
		}
	}

	static void populateStackNQueue(List<Node> nodesList, Queue<List<Integer>> queue, Stack<List<Integer>> stack,
			int level, int height) {
		if (nodesList.size() == 0) {
			return;
		}

		List<Node> childNodesList = new ArrayList<>();

		List<Integer> valuesList = new ArrayList<>(nodesList.size());

		for (Node node : nodesList) {
			valuesList.add(node.getValue());

			if (node.getLeft() != null) {
				childNodesList.add(node.getLeft());
			}

			if (node.getRight() != null) {
				childNodesList.add(node.getRight());
			}
		}

		if (level <= ((height + 1) / 2)) {
			queue.add(valuesList);
		} else {
			stack.add(valuesList);
		}

		populateStackNQueue(childNodesList, queue, stack, level + 1, height);
	}

	public static void main(String[] args) {
		Node root = new Node(1,
				new Node(2, new Node(4, new Node(8), new Node(9)), new Node(5, new Node(10), new Node(11))),
				new Node(3, new Node(6, new Node(12), new Node(13)), new Node(7, new Node(14), new Node(15))));
		printSpiral(root);
	}
}

class Node {
	private int value;
	private Node left;
	private Node right;

	public Node(int value) {
		super();
		this.value = value;
	}

	public Node(int value, Node left, Node right) {
		super();
		this.value = value;
		this.left = left;
		this.right = right;
	}

	public int getValue() {
		return value;
	}

	public void setValue(int value) {
		this.value = value;
	}

	public Node getLeft() {
		return left;
	}

	public void setLeft(Node left) {
		this.left = left;
	}

	public Node getRight() {
		return right;
	}

	public void setRight(Node right) {
		this.right = right;
	}
}