3.9 Binary Tree Level Order Traversal

Print a binary tree into array list in tree level order

Example

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

Return its level order traversal as:

[
  [3],
  [9,20],
  [15,7]
]

Logical Steps

Use queue to keep BFS running. The size of the queue before each iteration is the length of each level
In each iteration, add left and right node into queue, if they are not null

Code Template

public ArrayList<ArrayList<Integer>> levelOrder(TreeNode root) {
    ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>> ();

    // if root is empty, return empty result
    if (root == null)
        return result;

    // create a queue of TreeNodes for BFS
    LinkedList<TreeNode> queue = new LinkedList<TreeNode>();

    // initialization: add root to queue
    queue.add(root);

    // outer loop: keep BST running when queue is not empty
    while(!queue.isEmpty()) {
        ArrayList<Integer> level = new ArrayList<Integer>();

        // the size of the queue is the length of each level
        int size = queue.size();

        /**
         * pop all nodes from current level, and add the left and right
         * node into queue, if they're not empty
         */
        while(size > 0) {
            TreeNode curr = queue.pop();
            level.add(curr.val);

            if (curr.left != null)
                queue.offer(curr.left);

            if (curr.right != null)
                queue.offer(curr.right);

            size--;
        }

        // add current level into result
        result.add(new ArrayList(level));
    }

    return result;
}