Back to solutions

Binary Tree Level Order Traversal

MediumBinary Trees

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

Open problem
Constraints
  • 0 <= nodes <= 2000
  • -1000 <= Node.val <= 1000

Breadth-first search by level

Time O(n)Space O(n)

Process the tree with a queue. For each level, record the current queue size, pop exactly that many nodes into a row, and enqueue their children.

#include <bits/stdc++.h>
using namespace std;

struct TreeNode { int val; TreeNode* left; TreeNode* right; };

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