Binary Tree Level Order Traversal

NeetCode: Binary Tree Level Order Traversal · LeetCode: 102. Binary Tree Level Order Traversal · Difficulty: Medium

Return the values of a binary tree level by level, from left to right.

Example

Text

Input:  [3, 9, 20, null, null, 15, 7]    Output: [[3], [9, 20], [15, 7]]

Trees are given in LeetCode's level-order array form: the first value is the root, and each following pair of values holds the left and right child of the next node that exists, in the order the nodes were placed. null marks a missing child, and a missing node has no children listed. The tree(Integer...) helper in each program builds a TreeNode from such an array. TreeNode has the fields val, left, and right; a missing child is null, so no wrapper type is needed.

Brute force: recurse and file each value under its depth

A preorder walk that goes left before right visits each level's nodes left to right. Pass the current depth and add each value to the list for that depth. A new inner list is created the first time a depth is reached.

Java

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;
import java.util.Queue;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int val) {
        this.val = val;
    }
}

class Solution {
    private void walk(TreeNode node, int depth, List<List<Integer>> levels) {
        if (node == null) {
            return;
        }
        if (levels.size() == depth) {
            levels.add(new ArrayList<>());
        }
        levels.get(depth).add(node.val);
        walk(node.left, depth + 1, levels);
        walk(node.right, depth + 1, levels);
    }

    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> levels = new ArrayList<>();
        walk(root, 0, levels);
        return levels;
    }
}

public class Main {
    // Builds a tree from LeetCode's level-order array: null marks a missing child.
    static TreeNode tree(Integer... values) {
        if (values.length == 0 || values[0] == null) {
            return null;
        }
        TreeNode root = new TreeNode(values[0]);
        Queue<TreeNode> queue = new ArrayDeque<>();
        queue.add(root);
        int i = 1;
        while (!queue.isEmpty() && i < values.length) {
            TreeNode node = queue.remove();
            if (i < values.length && values[i] != null) {
                node.left = new TreeNode(values[i]);
                queue.add(node.left);
            }
            i++;
            if (i < values.length && values[i] != null) {
                node.right = new TreeNode(values[i]);
                queue.add(node.right);
            }
            i++;
        }
        return root;
    }

    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.levelOrder(tree(3, 9, 20, null, null, 15, 7)));
        System.out.println(s.levelOrder(tree()));
    }
}

Output

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

Time: O(n). Space: O(h) for the recursion plus the output.

Optimal: BFS with a queue

A queue naturally processes nodes in level order. At the start of each round, the queue holds exactly one level, so read queue.size() once at the start of the round, take that many nodes, record their values, and enqueue their children for the next round. This avoids deep recursion. ArrayDeque is used as a queue through add and remove. It rejects null, so only non-null children are added.

Java

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;
import java.util.Queue;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int val) {
        this.val = val;
    }
}

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        Queue<TreeNode> queue = new ArrayDeque<>();
        if (root != null) {
            queue.add(root);
        }
        while (!queue.isEmpty()) {
            int size = queue.size(); // nodes in the current level
            List<Integer> level = new ArrayList<>();
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.remove();
                level.add(node.val);
                if (node.left != null) {
                    queue.add(node.left);
                }
                if (node.right != null) {
                    queue.add(node.right);
                }
            }
            result.add(level);
        }
        return result;
    }
}

public class Main {
    // Builds a tree from LeetCode's level-order array: null marks a missing child.
    static TreeNode tree(Integer... values) {
        if (values.length == 0 || values[0] == null) {
            return null;
        }
        TreeNode root = new TreeNode(values[0]);
        Queue<TreeNode> queue = new ArrayDeque<>();
        queue.add(root);
        int i = 1;
        while (!queue.isEmpty() && i < values.length) {
            TreeNode node = queue.remove();
            if (i < values.length && values[i] != null) {
                node.left = new TreeNode(values[i]);
                queue.add(node.left);
            }
            i++;
            if (i < values.length && values[i] != null) {
                node.right = new TreeNode(values[i]);
                queue.add(node.right);
            }
            i++;
        }
        return root;
    }

    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.levelOrder(tree(3, 9, 20, null, null, 15, 7)));
        System.out.println(s.levelOrder(tree()));
    }
}

Output

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

Time: O(n). Space: O(w) for the widest level, plus the output.