Binary Tree Level Order Traversal

mediumTrees: Traversal51 stepsJava · Python · C++

Return node values level by level, left to right. Use a queue: at the start of each round, the queue holds exactly one level. Pop that many nodes, record their values, and push their children for the next level.

▶ Watch the animated trace

Traced input: root = [3, 9, 20, null, null, 15, 7] → [[3], [9, 20], [15, 7]]. Original problem: neetcode.io/problems/level-order-traversal-of-binary-tree

Complexity

BestO(n)

AverageO(n)

WorstO(n)

SpaceO(w)

w = the widest level, up to n/2.

Key idea

A queue processes nodes in the order they were discovered: breadth-first.
Snapshot size = queue.size() to know where the current level ends.
Children are added left before right.

Common mistakes

Forgetting the size snapshot mixes levels together.
Adding null children to the queue.

Solution

Java

List<List<Integer>> levelOrder(TreeNode root) {
    List<List<Integer>> res = new ArrayList<>();
    if (root == null) return res;
    Queue<TreeNode> queue = new ArrayDeque<>();
    queue.offer(root);
    while (!queue.isEmpty()) {
        int size = queue.size();
        List<Integer> level = new ArrayList<>();
        for (int i = 0; i < size; i++) {
            TreeNode node = queue.poll();
            level.add(node.val);
            if (node.left != null) queue.offer(node.left);
            if (node.right != null) queue.offer(node.right);
        }
        res.add(level);
    }
    return res;
}

Python

def levelOrder(root: Optional[TreeNode]) -> List[List[int]]:
    res = []
    if not root: return res
    queue = deque([root])
    while queue:
        level = []
        for _ in range(len(queue)):
            node = queue.popleft()
            level.append(node.val)
            if node.left: queue.append(node.left)
            if node.right: queue.append(node.right)
        res.append(level)
    return res

C++

vector<vector<int>> levelOrder(TreeNode* root) {
    vector<vector<int>> res;
    if (!root) return res;
    queue<TreeNode*> q;
    q.push(root);
    while (!q.empty()) {
        vector<int> level;
        for (int i = q.size(); i > 0; i--) {
            TreeNode* node = q.front(); q.pop();
            level.push_back(node->val);
            if (node->left) q.push(node->left);
            if (node->right) q.push(node->right);
        }
        res.push_back(level);
    }
    return res;
}

Edge cases

Each one has its own trace in the interactive view.

Case	Input	Answer
Empty tree Return an empty list.	`root = []`	`[]`
Single node One level.	`root = [1]`	`[[1]]`
Skewed Each level has one node.	`root = [1, 2, null, 3]`	`[[1], [2], [3]]`