CareerCup

my solution, extrac data structure : 1 queue 2 stack

struct TreeNode
{
      int    Element;
      TreeNode *Left;
      TreeNode *Right;
      TreeNode *Third;
}  *NodePosition;

void	ZigZag(NodePosition root)
{
	queue<NodePosition> que;
	stack<NodePosition>  stk;
	bool	level = true; // level indicator
	que.push(root);
	que.push(NULL);
	NodePosition prev = NULL;
	NodePosition curr = NULL;

	while(!que.empty())
	{
		//1. Dequeue
		curr = que.front();
		que.pop();

		//2. Reach level end
		if (curr == NULL)
		{
			// put element in stack to queue
			while(!stk.empty())
			{
				que.push(stk.top());
				stk.pop();
			}
			level = level == true ? false : true;  // change level indicator alternately
			if(que.empty())
				break;
			que.push(NULL);
			curr = que.front();
			que.pop();
		}

		//3. Put current node’s children to stack
		if(level)
		{
			if(curr->Left)
				stk.push(curr->Left);
			if(curr->Right)
				stk.push(curr->Right);
		}
		else
		{
			if(curr->Right)
				stk.push(curr->Right);
			if(curr->Left)
				stk.push(curr->Left);
		}

		// 4. Make prev’s third pointer point to current node
		if(prev)
			prev->Third = curr;
		prev = curr;
	}
	prev->Third = NULL;
}

Modified BFS.
Use a stack to store the nodes of same level (Push in alternate order)
Level 2 : Push right to left
Level 3 : Push left to right
..
Pop the nodes from the stack and enqueue it only when the queue has become empty.

This can be done in place without additional space. Assume level n's pointers are fixed. Using these pointers, we can fix the pointers for level n+1. Explicitly fix the pointers for level 0 alone. Once it is done, apply above mentioned strategy.

Can we use a queue?
Enqueue the root first,
when dequeue a node, enqueue its left and right nodes.

I want the code

Solution without additional memory.

public class MainClass {

    public static void main(String[] args) {
        TreeItem root = init();

        linkLevel(root, true);

        printTree(root);
    }

    private static void linkLevel(TreeItem startNode, boolean direction) {
        TreeItem currentNode = startNode;

        TreeItem lastSibling = null;
        do {
            if (direction) {
                if (currentNode.left != null) {
                    currentNode.left.sibling = lastSibling;
                    if (currentNode.right != null) {
                        currentNode.right.sibling = currentNode.left;
                        lastSibling = currentNode.right;
                    } else {
                        lastSibling = currentNode.left;
                    }
                } else if (currentNode.right != null) {
                    currentNode.right.sibling = lastSibling;
                    lastSibling = currentNode.right;
                }
            } else {
                if (currentNode.right != null) {
                    currentNode.right.sibling = lastSibling;
                    if (currentNode.left != null) {
                        currentNode.left.sibling = currentNode.right;
                        lastSibling = currentNode.left;
                    } else {
                        lastSibling = currentNode.right;
                    }
                } else if (currentNode.left != null) {
                    currentNode.left.sibling = lastSibling;
                    lastSibling = currentNode.left;
                }
            }
            if (currentNode.sibling == null) {
                currentNode.sibling = lastSibling;
                break;
            } else {
                currentNode = currentNode.sibling;
            }
        } while (true);

        if (lastSibling != null) linkLevel(lastSibling, !direction);
    }

    private static void printTree(TreeItem item) {
        while (item != null) {
            System.out.print(item.value);
            System.out.print(" ");
            item = item.sibling;
        }
    }

    private static TreeItem init() {
        TreeItem A = new TreeItem("A");
        TreeItem B = new TreeItem("B");
        TreeItem C = new TreeItem("C");
        TreeItem D = new TreeItem("D");
        TreeItem E = new TreeItem("E");
        TreeItem F = new TreeItem("F");

        A.left = B;
        A.right = C;
        B.left = D;
        B.right = E;
        C.right = F;
        return A;
    }

    public static class TreeItem {
        public TreeItem left;
        public TreeItem right;
        public TreeItem sibling;
        public String value;

        public TreeItem(String value) {
            this.value = value;
        }

        @Override
        public String toString() {
            return value;
        }
    }

}

Can we do with reverse level order traversal in zig zag form?