Returning Binary Search Tree Nodes in Zig Zag manner

Question

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

}

• abuzittin gillifirca: Time and Space complexity is never stated as O(3n) or O(2n). O(a*n + b) = O(n).

Answer 1

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.