ZigZag order of a tree traversal

Question

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

                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);
                    }
                }
            }
        }
        return res;
    }

Answer 1

Just the first few steps of refactoring:

1. ArrayList<...> reference types should be simply List<...>:

   List<List<Integer>> res = new ArrayList<>();
   

   See: Effective Java, 2nd edition, Item 52: Refer to objects by their interfaces

2. This variable is never used, remove it:

   TreeNode empty = new TreeNode(2);
   

3. I would avoid abbreviations like res, curr and val. They are not too readable and I suppose you have autocomplete (if not, use an IDE, it helps a lot), so using longer names does not mean more typing but it would help readers and maintainers a lot since they don't have to remember the purpose of each variable - the name would express the programmers intent and would not force readers to decode the abbreviations every time they read/maintain the code.

   Furthermore, if you type resu and press Ctrl+Space for autocomplete in Eclipse it founds nothing which is rather disturbing.

4. These two lines are duplicated:

   level.add(curr.left.val);
   queue.add(curr.left);
   

   You could extract out a method for that:

    private void visit(List<Integer> level, Queue<TreeNode> queue, TreeNode left) {
       level.add(left.val);
       queue.add(left);
   }
   

5. After that you might notice the similarity between the method above and the body of the following if statement:

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

   You could use the same method here too:

   if (curr.right != null) {
       visit(level, queue, curr.right);
   }
   

   Of course, renaming the method's parameter will increase clarity:

   private void visit(List<Integer> level, Queue<TreeNode> queue, TreeNode node) {
       level.add(node.val);
       queue.add(node);
   }
   

6. So, currently the end of the original method looks like the following:

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

   You could remove some more duplication by moving the null check into the visit method:

   private void visit(List<Integer> level, Queue<TreeNode> queue, TreeNode node) {
       if (node == null) {
           return;
       }
       level.add(node.val);
       queue.add(node);
   }
   

   (I've used a guard clause here to make the code flatten.)

   Usage:

   if (depth % 2 == 0) {
       visit(level, queue, currentNode.left);
       visit(level, queue, currentNode.right);
   } else {
       visit(level, queue, currentNode.right);
       visit(level, queue, currentNode.left);
   }
   

7. I would also invert the condition here to get a guard clause:

   if(!queue.isEmpty()){
       queue.add(null);
   }
   else{
       break;
   }
   

   Result:

   if (queue.isEmpty()) {
       break;
   }
   queue.add(null);
   

8. There are seven lines between the declaration of the queue and its first usage:

   Queue<TreeNode> queue = new LinkedList<>();
   if (root == null) {
       return result;
   }
   List<Integer> level = new ArrayList<Integer>();
   level.add(root.val);
   result.add(level);
   int depth = 1;
   queue.add(root);
   

   It could have smaller scope and could be closer to its first usage:

   if (root == null) {
       return result;
   }
   List<Integer> level = new ArrayList<Integer>();
   level.add(root.val);
   result.add(level);
   int depth = 1;
   Queue<TreeNode> queue = new LinkedList<>();
   queue.add(root);
   

   (Effective Java, Second Edition, Item 45: Minimize the scope of local variables)

Answer 2

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