ZigZag order of a tree traversal

Please let me know your thoughts on the code below, please be brutal. Here is the question I solved:

Given a binary tree, return the zigzag level order traversal of its nodes' values. (ie, from left to right, then right to left for the next level and alternate between).

For example:
Given binary tree {3,9,20,#,#,15,7},

3
   / \
  9  20
    /  \
   15   7

return its zigzag level order traversal as:
[
[3],
[20,9],
[15,7]
]

```
public ArrayList> zigzagLevelOrder(TreeNode root) {
ArrayList> res = new ArrayList<>();
Queue queue = new LinkedList<>();
if(root==null){
return res;
}
ArrayList level = new ArrayList();
level.add(root.val);
res.add(level);
int depth=1;
queue.add(root);
TreeNode empty = new TreeNode(2);
queue.add(null);
level = new ArrayList();
while(!queue.isEmpty()){
TreeNode curr = queue.poll();
if(curr==null){
if(!queue.isEmpty()){
queue.add(null);
}
else{
break;
}
res.add(level);
level = new ArrayList();

depth++;
}
else{
if(depth%2==0){
if(curr.left!=null){
level.add(curr.left.val);
queue.add(curr.left);
}
if(curr.right!=null){
level.add(curr.right.val);
queue.add(curr.right);

}
}
else{
if(curr.right!=null){
level.add(curr.right.val);
queue.add(curr.right);
}
if(curr.left!=null){
level.add(curr.left.val);
queue.add(curr.left);
}

Branching to change behavior is a code smell. A cleaner design would be to use the State pattern, and let the state toggle each time you descend to the next layer of the tree.

Also, I think you've made things less clear by tangling your traversal logic, with your output logic. Which is to say, instead of doing something with the child, and something with the child values, instead of working with the parent value and adding the children to the traversal tree.

In pseudo code, I would expect the logic to look like

currentNodes = [ root ]
while( currentNodes.notEmpty ) {
    state = state.switch
    valueList = report.nextValues

    nextNodes = []

    for ( node : currentNodes ) {
        valueList.add(node.value)

        nextNodes.add( state.order(node.left, node.right) )
    }
    currentNodes = nextNodes.reverse;
}

return report

StackExchange Code Review Q#45893, answer score: 2