I tried to implement an answer for the algorithm question given below. I implemented two different solutions. I couldn't decide which one is better. ( Maybe none )Note: Node class and ZigZag interface are given along with the question.Problem Definition A binary tree is given. Return a list of nodes in Zig Zag manner. state the Big-O runtime and space complexity of your implementation.import java.util.ArrayList;import java.util.HashMap;import java.util.List;import java.util.LinkedList;import java.util.Map;import java.util.Stack;import java.util.Queue;import java.util.Collections;/** * Print a binary tree in zig zag way... that is: * ......a......... * ....b....c....... * ..d...e...f...g.. * .h.i.j.k.l.m.n.o. *  * should be printed as a-c-b-d-e-f-g-o-n-m-l-k-j-i-h *  * what data structure will u use for that? *  */public class BinaryZigZagTraversal {/* ------------------------------------------------------------- *//* DATA DEFINITION(S) *//* ------------------------------------------------------------- *//** * ZigZag interface instance */private ZigZag zigZagInstance;/** * Tree node *  */public class Node {    private int value;    private Node left;    private Node right;    public Node(int value, Node left, Node right) {        this.value = value;        this.left = left;        this.right = right;    }    public int getValue() {        return this.value;    }    public Node getLeft() {        return this.left;    }    public Node getRight() {        return this.right;    }    protected void setLeft(Node leftNode) {        this.left = leftNode;    }    protected void setRight(Node rightNode) {        this.right = rightNode;    }    @Override    public String toString() {        return String.valueOf( getValue() );    }}/** * ZigZag interface *  */public interface ZigZag {    public List<Node> GetZigZagOrder(Node rootNode);}/* ------------------------------------------------------------- *//* SOLUTION- 1 *//* ------------------------------------------------------------- *//** * My BFS-like Implementation *  * @author ozkansari * * Total Time complexity: O(2n) -> n+n+(n/8) * Total Space complexity: O(3n) -> size(bfsQueue) + size(resultList) + size(levelNodes)  */public class ZigZagBFSImpl implements ZigZag {    @Override    public List<Node> GetZigZagOrder(Node rootNode) {        Queue<Node> bfsQueue = new LinkedList<Node>();        List<Node> resultList = new ArrayList<Node>();        bfsQueue.add(rootNode);        int currentLevel = 1;        while(!bfsQueue.isEmpty()) {            // O(n)            // Remove all first            List<Node> levelNodes = new ArrayList<Node>();            while(!bfsQueue.isEmpty()) {                Node n = bfsQueue.remove();                levelNodes.add(n);            }            // O(n)            boolean hasChildNode = false;            for (Node currentNode : levelNodes) {                Node firstNode = currentNode.getLeft();                Node secondNode = currentNode.getRight();                if(firstNode!=null) {                    bfsQueue.add( firstNode );                    hasChildNode=true;                }                if(secondNode!=null) {                    bfsQueue.add( secondNode );                    hasChildNode=true;                }            }            // O(n/8)            if(currentLevel%2==0) {                Collections.reverse(levelNodes);            }            resultList.addAll(levelNodes);            if(hasChildNode) {                currentLevel++;            }        }        return resultList;    }}/* ------------------------------------------------------------- *//* SOLUTION- 2 *//* ------------------------------------------------------------- *//** * My ZigZag Implementation *  * @author ozkansari * * Total Time complexity: O(n) -> n+n * Total Space complexity: O(n) -> size(levels) */public class ZigZagStackImpl implements ZigZag {    /**     * Map of stacks to represent tree levels     */    Map<Integer,Stack<Node>> levels=new HashMap<Integer,Stack<Node>>();    @Override    public List<Node> GetZigZagOrder(Node rootNode) {        // Initialize next level        initLevels(rootNode, 1);        // Find result list        List<Node> resultList = new ArrayList<Node>();        for (int i=1; ; i++) {            Stack<Node> levelStack = levels.get(i);            if(levelStack==null) break;            while(!levelStack.empty()) {                Node currentNode = null;                if(i%2==0) { // right side                    currentNode = levelStack.pop();                } else {                    currentNode = levelStack.firstElement();                    levelStack.remove(currentNode);                }                resultList.add(currentNode);            }        }        return resultList;    }    /**     * Helper recursive method     *     * @param currentNode     * @param currentLevel     */    private void initLevels(Node currentNode, Integer levelIndex) {        if(levelIndex<=0) {            levelIndex=1;        }        // Initialize first root level if required        if(levelIndex==1){            Stack<Node> rootLevel = new Stack<Node>();            rootLevel.add(currentNode);            levels.put(1,rootLevel);            levelIndex=2;        }        Node leftNode = currentNode.getLeft();        Node rightNode = currentNode.getRight();        if(leftNode==null && rightNode==null) {            return;        }         Stack<Node> currentLevel = levels.get(levelIndex);        if(currentLevel==null) {            currentLevel = new Stack<Node>();            levels.put(levelIndex,currentLevel);        }        if(leftNode!=null) {            currentLevel.push(leftNode);            if(leftNode.getLeft()!=null || leftNode.getRight()!=null) {                initLevels(leftNode,levelIndex+1);            }         }        if(rightNode!=null) {            currentLevel.push(rightNode);            if(rightNode.getLeft()!=null || rightNode.getRight()!=null) {                initLevels(rightNode,levelIndex+1);            }        }    }}/** *  * @return ZigZag instance */public ZigZag getZigZagInstance(){    if(zigZagInstance==null) {        zigZagInstance = new ZigZagBFSImpl();    }    return zigZagInstance;}/* ------------------------------------------------------------- *//* TEST METHOD(S) *//* ------------------------------------------------------------- *//** * Main method to test the ZigZag coding sample.  * I actually prefer to test my code using JUnit but the result is requested to be in one file. *  * @author ozkansari *  */public String test(int nodeCount) {    ZigZag zigZagImpl = getZigZagInstance();    List<Node> zigZagOrderedList = zigZagImpl.GetZigZagOrder(generateDummyBinaryTree(nodeCount));    StringBuffer sbf = new StringBuffer();    for (Node node : zigZagOrderedList) {        sbf.append(node +  );    }    System.out.println(sbf.toString());    return sbf.toString();}/** * Generates a dummy binary tree and returns its root node *  */private Node generateDummyBinaryTree(int nodeCount){    List<Node> sampleData = new ArrayList<Node>();    for(int i=1;i<=nodeCount;i++) {        Node currentNode = new Node(i,null,null);;        sampleData.add(currentNode);    }    int j=1;    for (Node node : sampleData) {        int index = j*2;        Node rightNode = index+1<=sampleData.size() ? sampleData.get(index) : null;        Node leftNode = index<=sampleData.size() ? sampleData.get(index-1) : null;        node.setRight(rightNode);        node.setLeft(leftNode);        j++;    }    return sampleData.get(0);}/** * Main method to test my sample code. *  * @param args */public static void main(String[] args) {    BinaryZigZagTraversal z = new BinaryZigZagTraversal ();    System.out.println( z.test(1).equals(1 ) );    System.out.println( z.test(2).equals(1 2 ) );    System.out.println( z.test(4).equals(1 3 2 4 ) );    System.out.println( z.test(12).equals(1 3 2 4 5 6 7 12 11 10 9 8 ) );    System.out.println( z.test(16).equals(1 3 2 4 5 6 7 15 14 13 12 11 10 9 8 16 ) );    System.out.println( z.test(24).equals(1 3 2 4 5 6 7 15 14 13 12 11 10 9 8 16 17 18 19 20 21 22 23 24 ) );}}
Returning Binary Search Tree Nodes in Zig Zag manner
java;binary search
First of all you are not really using Queue and Stack in any specific way.The following :currentNode = levelStack.firstElement();levelStack.remove(currentNode);can be more concisely expressed as:currentNode = levelStack.remove(0);In any case removing the first element of a Stack is slow.If you are going to remove elements from both ends of a list (as is the case with levelStack) you should use a Deque. LinkedList implements Deque. The following :         List<Node> levelNodes = new ArrayList<Node>();while(!bfsQueue.isEmpty()) {    Node n = bfsQueue.remove();    levelNodes.add(n);}can be more concisely expressed as:List<Node> levelNodes = new ArrayList<Node>(bfsQueue);ZigZagBFSImpl is O(n), but ZigZagStackImpl is > O(n) (due to stack.remove(first-element) being O(stack-size))Generally avoid StringBuffer in favor of StringBuilder , because of synchronization overhead.Throw IllegalArgumentException for illegal arguments instead of continuing execution with unexpected behaviour :if(levelIndex<=0) {    levelIndex=1;}Integer levelIndex should be int levelIndex since passing in null causes an exception, and therefore not a valid argument.