# Returning Binary Search Tree Nodes in Zig Zag manner

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.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) {

List<Node> resultList = new ArrayList<Node>();

int currentLevel = 1;
while(!bfsQueue.isEmpty()) {

// O(n)
// Remove all first
List<Node> levelNodes = new ArrayList<Node>();
while(!bfsQueue.isEmpty()) {
Node n = bfsQueue.remove();
}

// O(n)
boolean hasChildNode = false;
for (Node currentNode : levelNodes) {
Node firstNode = currentNode.getLeft();
Node secondNode = currentNode.getRight();

if(firstNode!=null) {
hasChildNode=true;
}

if(secondNode!=null) {
hasChildNode=true;
}

}

// O(n/8)
if(currentLevel%2==0) {
Collections.reverse(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);
}

}

}

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


}

-
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

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


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.

-