Binary Tree Level Order Traversal

Question (LC.102)

Given a binary tree, return thelevel ordertraversal of its nodes' values. From left to right, level by level.

Example

    3
   / \
  9  20
    /  \
   15   7
Output: [ [3], [9, 20], [15, 7] ]

Analysis

We need to do a breadth-first search on a binary tree. Should be pretty standard. Create List<List<Integer>> results to hold the results and at each level create List<Integer> level to hold values at that level.

Code 1

public void levelOrder(TreeNode root) {
    if (root == null) {
        return;
    }

    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);

    while (!queue.isEmpty()) {
        TreeNode current = queue.poll();
        System.out.println(current.val);
        if (current.left != null) {
            queue.offer(current.left);
        }
        if (current.right != null) {
            queue.offer(current.right);
        }
    }
}

Note: Queue is an interface in Java. Instantiating an interface doesn't make sense. Instead we want to choose an existing collection implementation.

Note2: ArrayDeque is another option. It uses a circular linked list to store the nodes. And resize when necessary.

Code 2

Now we can print out the nodes in level order. But how do we separate them by their respecting levels? We need to figure out the size at each level.

public List<List<Integer>> levelOrder(TreeNode root) {
    List<List<Integer>> results = new ArrayList<>();
    if (root == null) {
        return results;
    }
    Queue<TreeNode> queue = new LinkedList<>();
    List<Integer> level;
    queue.offer(root);
    TreeNode current;
    while (!queue.isEmpty()) {
        level = new ArrayList<>();
        // level size changes after enqueue and dequeue
        // so we have to store this outside of the loop
        int levelSize = queue.size();
        for (int i = 0; i < levelSize; i++) {
            current = queue.poll();
            level.add(current.val);
            if (current.left != null) {
                queue.offer(current.left);
            }
            if (current.right != null) {
                queue.offer(current.right);
            }                
        }
        results.add(level);
    }
    return results;
}

def levelOrder(self, root: TreeNode) -> List[List[int]]:
    
    results: List[List[int]] = []
    
    if root == None:
        return results 
    
    queue: Deque[root] = deque()
    queue.append(root)
    
    while len(queue) > 0:
        level_size = len(queue)
        level_result: List[int] = []
        for i in range(level_size):
            cur_node = queue.popleft()
            level_result.append(cur_node.val)
            if cur_node.left:
                queue.append(cur_node.left)
            if cur_node.right:
                queue.append(cur_node.right)
        results.append(level_result)
    return results 

Follow Up (LC.107)

Given a binary tree, return the bottom-up level order traversal of its nodes' values. From left to right, level by level from leaf to root.

Example

    3
   / \
  9  20
    /  \
   15   7
 Output: [ [15, 7], [9, 20], [3] ]

Analysis

Either add in the level to the front of the list results.add(0, level) or reverse the results before return it Collections.reverse(results).

References

ArrayDeque Implementation by Jack Han