CareerCup

Seems like a DFS.

That is not spiral..

This can be done using a BFS pattern. The tree levels can be printed from bottom to top (root). Direction of printing needs to be adjusted (forward/backward). Here is a C# implementation

class Node<T>
{
public T data;
public Node<T> left, right;
}

static void PrintReverseSpiral<T>(Node<T> root)
{
List<Node<T>> current = new List<Node<T>>();
List<Node<T>> next = new List<Node<T>>();
List<List<Node<T>>> levels = new List<List<Node<T>>>();

if (root != default(Node<T>))
    current.Add(root);

// build a list of all the levels
while (current.Count > 0)
{
    foreach (Node<T> n in current)
    {
        if (n.left != null) next.Add(n.left);
        if (n.right != null) next.Add(n.right);
    }

    levels.Add(new List<Node<T>>(current));
    current = next;
    next = new List<Node<T>>();
}

// print in spiral order
for (int i = levels.Count - 1; i >= 0; i--)
{
    if (i % 2 == 0)
    {
        // even levels printed forward
        for (int j = 0; j < levels[i].Count; j++)
            Console.Write("{0}, ", levels[i][j].data);
    }
    else
    {
        // odd levels printed backward
        for (int j = levels[i].Count - 1; j >= 0 ; j--)
            Console.Write("{0}, ", levels[i][j].data);
    }
}

Console.WriteLine();
}

// C++ implementation of a O(n) time method for spiral order traversal
#include <iostream>
#include <stack>
using namespace std;
 
// Binary Tree node
struct node
{
    int data;
    struct node *left, *right;
};

// A utility functiont to create a new node
struct node* newNode(int data)
{
    struct node* node = new struct node;
    node->data = data;
    node->left = NULL;
    node->right = NULL;
 
    return(node);
}
 
void printSpiral(struct node *root)
{
    if (root == NULL)  return;   // NULL check
	struct node *temp;
    // Create two stacks to store alternate levels
	// Here stack stores tree node pointers
    stack<struct node*> s1;  // For levels to be printed from right to left
    stack<struct node*> s2;  // For levels to be printed from left to right
	stack<struct node*> s3;  // To store the end result, and print it in reverse order 
    // Push first level to first stack 's1'
    s1.push(root);
 
    // Keep ptinting while any of the stacks has some nodes
    while (!s1.empty() || !s2.empty())
    {
        // Print nodes of current level from s1 and push nodes of
        // next level to s2
        while (!s1.empty())
        {
            temp = s1.top(); 
            s1.pop();
            //cout << temp->data << " ";
			s3.push(temp);
            // Note that is right is pushed before left
            if (temp->right)
                s2.push(temp->right);
            if (temp->left)
                s2.push(temp->left);
        }
 
        // Print nodes of current level from s2 and push nodes of
        // next level to s1
        while (!s2.empty())
        {
            temp = s2.top();
            s2.pop();
            //cout << temp->data << " ";
			s3.push(temp);
            // Note that is left is pushed before right
            if (temp->left)
                s1.push(temp->left);
            if (temp->right)
                s1.push(temp->right);
        }
    }
	// Print tree elements in reverse order
	while(!s3.empty())
	{	
		temp = s3.top(); // retrun top element
		s3.pop(); // pop doesn't return anyhting , just removes top element.   
		cout<<temp->data<<" ";
	}
}
 
 
int main()
{
    struct node *root = newNode(1);
    root->left        = newNode(2);
    root->right       = newNode(3);
    root->left->left  = newNode(7);
    root->left->right = newNode(6);
    root->right->left  = newNode(5);
    root->right->right = newNode(4);
    cout << "Spiral Order traversal of binary tree is \n";
    printSpiral(root);
 
    return 0;
}

Java code for reverse spiral order traversal :
Node is as following

public class Node {

	private int key;
	private Node left;
	private Node right;

	public Node(int key) {
		this.key = key;
	}

	public int getKey() {
		return key;
	}

	public void setKey(int key) {
		this.key = key;
	}

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

	@Override
	public String toString() {
		return "Node [key=" + key + ", left=" + left + ", right=" + right + "]";
	}

}

reverseSpiralLevelOrder is given below :

public static void reverseSpiralLevelOrder(Node root) {
		boolean isLeftToRightTraversal = true;
		int height = height(root);
		for (int i = height; i >= 1; i--) {
			spiralLevelOrder(root, i, isLeftToRightTraversal);
			isLeftToRightTraversal = !isLeftToRightTraversal;
		}
	}

	private static void spiralLevelOrder(Node root, int level, boolean isLeftToRightTraversal) {
		if (root == null) {
			return;
		}
		if (level == 1) {
			System.out.println(root.getKey() + " ");
		} else {
			if (isLeftToRightTraversal) {
				spiralLevelOrder(root.getLeft(), level - 1, isLeftToRightTraversal);
				spiralLevelOrder(root.getRight(), level - 1, isLeftToRightTraversal);
			} else {
				spiralLevelOrder(root.getRight(), level - 1, isLeftToRightTraversal);
				spiralLevelOrder(root.getLeft(), level - 1, isLeftToRightTraversal);
			}
		}

}