Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

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

}

share|improve this question
1  
Time and Space complexity is never stated as O(3n) or O(2n). O(a*n + b) = O(n). –  abuzittin gillifirca Jan 7 '13 at 10:03
    
Thanks. You are right. –  ozkansari Jan 7 '13 at 12:30
add comment

1 Answer 1

up vote 1 down vote accepted
  1. First of all you are not really using Queue and Stack in any specific way.
  2. The following :

    currentNode = levelStack.firstElement();
    levelStack.remove(currentNode);
    

    can be more concisely expressed as:

    currentNode = levelStack.remove(0);
    
  3. In any case removing the first element of a Stack is slow.

  4. 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.

  5. 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);
    
  6. ZigZagBFSImpl is O(n), but ZigZagStackImpl is > O(n) (due to stack.remove(first-element) being O(stack-size))

  7. Generally avoid StringBuffer in favor of StringBuilder , because of synchronization overhead.

  8. Throw IllegalArgumentException for illegal arguments instead of continuing execution with unexpected behaviour :

    if(levelIndex<=0) {
        levelIndex=1;
    }
    
  9. Integer levelIndex should be int levelIndex since passing in null causes an exception, and therefore not a valid argument.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.