Leetcode: Binary Tree Level Order Traversal

Given a binary tree, return the level order traversal of its nodes' values. (ie, from left to right, level by level).

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

    3
   / \
  9  20
    /  \
   15   7

return its level order traversal as:

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

confused what "{1,#,2,3}" means? > read more on how binary tree is serialized on OJ.

Understand the problem:

The question asks for a BFS, i.e, level order traversal of a binary tree. Note that the format of the output should represent t he layer information, which is a list of a list. 

Recursive Solution:

The recursive solution is very similar to DFS. The difference is we should store the layer information for each node. We can use the preorder traversal. For each level, we check if this level exists in the final result list, if not, create a new list; else, append the node into the corresponding list.

Code (Java):

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ArrayList<ArrayList<Integer>> levelOrder(TreeNode root) {
        ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
        
        levelOrder(root, result, 1);
        
        return result;
    }
    
    private void levelOrder(TreeNode node, ArrayList<ArrayList<Integer>> result, int level) {
        if (node == null) return;
        
        if (result.size() < level) {
            ArrayList<Integer> temp = new ArrayList<Integer>();
            temp.add(node.val);
            result.add(temp);
        } else {
            result.get(level - 1).add(node.val);
        }
        
        levelOrder(node.left, result, level + 1);
        levelOrder(node.right, result, level + 1);
    }
}

Discussion:
The time complexity is O(n) since we traverse all elements of the tree. The space complexity is O(logn) since the recursive preorder traversal.

Iterative Solution:
In the iterative solution, we use a queue. For each element traversed, we enqueue both its left child and right child. Then we enter into the next level and dequeue all the elements of the queue.

Code (Java):

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ArrayList<ArrayList<Integer>> levelOrder(TreeNode root) {
        ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
        if (root == null) return result;
        
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            ArrayList<Integer> levelList = new ArrayList<Integer>();
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode curr = queue.poll();
                levelList.add(curr.val);
                if (curr.left != null) {
                    queue.offer(curr.left);
                }
                if (curr.right != null) {
                    queue.offer(curr.right);
                }
            }
            result.add(levelList);
        }
        return result;
    }
}

Discussion:
The time complexity of the iterative solution is O(n). The space complexity is a bit of tricky. Suppose we have a full tree, so the bottom level of the tree (leaves) has the most number of nodes. Since we use a queue to store the nodes at each level, at each level, we dequeued all nodes at current level, and enqueued nodes for the next level. So the maximal number of elements in the queue is the number of leaves. Suppose the height of the tree is h, we know that the number of leaves is 2^(h-1). Since h = logn, so the number of leaves is 1/2 n. So the number of elements in the queue is bounded by 1/2 O(n), which equals to O(n).

Summary:
So far we learned all basic tree traversal approaches, DFS and BFS. The recursive BFS is a bit of tricky, which is still DFS but store the level information. The iterative BFS is easier to understand. Remember the use of the queue.