Practice › Trees
Level Order Traversal
Easy · Trees · Asked at Amazon, Microsoft, Google, Meta
Print the tree level by level, one level per line, left to right.
Input
First line: k. Second line: k values — the tree in level order, -1 means no node.
Output
One line per level with its values space-separated.
Constraints
- 1 ≤ number of nodes ≤ 10^4
BFS with a queue; process the queue one level (its current size) at a time.
Example 1
Input
7 3 9 20 -1 -1 15 7
Output
3 9 20 15 7
Example 2
Input
1 1
Output
1
Hints
- Breadth-first search visits nodes level by level — use a queue.
- To separate levels, look at the queue size at the start of each round: exactly that many nodes form the current level.
Approach
Start with the root in a queue. Each round, read size = queue.size(), pop exactly that many nodes (the current level), print them on one line and push their children. The children form the next level. The loop ends when the queue is empty.
Complexity: O(n) time · O(width) space
Solution
C++ solution
#include <bits/stdc++.h>
using namespace std;
struct Node {
long long val;
Node *left = nullptr, *right = nullptr;
Node(long long v) : val(v) {}
};
// Build a tree from level order where -1 means "no node".
Node *readTree() {
int k;
cin >> k;
vector<long long> v(k);
for (auto &x : v) cin >> x;
if (k == 0 || v[0] == -1) return nullptr;
Node *root = new Node(v[0]);
queue<Node *> q;
q.push(root);
int i = 1;
while (!q.empty() && i < k) {
Node *cur = q.front();
q.pop();
if (i < k && v[i] != -1) q.push(cur->left = new Node(v[i]));
i++;
if (i < k && v[i] != -1) q.push(cur->right = new Node(v[i]));
i++;
}
return root;
}
int main() {
Node *root = readTree();
queue<Node *> q;
if (root) q.push(root);
while (!q.empty()) {
int size = q.size();
for (int i = 0; i < size; i++) {
Node *cur = q.front();
q.pop();
cout << cur->val << (i + 1 < size ? " " : "\n");
if (cur->left) q.push(cur->left);
if (cur->right) q.push(cur->right);
}
}
return 0;
}Python solution
import sys
from collections import deque
class Node:
def __init__(self, val):
self.val, self.left, self.right = val, None, None
def read_tree():
"""Build a tree from level order where -1 means "no node"."""
data = list(map(int, sys.stdin.read().split()))
k, v = data[0], data[1 : data[0] + 1]
if not v or v[0] == -1:
return None
root = Node(v[0])
q, i = deque([root]), 1
while q and i < k:
cur = q.popleft()
if i < k and v[i] != -1:
cur.left = Node(v[i])
q.append(cur.left)
i += 1
if i < k and v[i] != -1:
cur.right = Node(v[i])
q.append(cur.right)
i += 1
return root
root = read_tree()
level = [root] if root else []
while level:
print(*(node.val for node in level))
level = [child for node in level for child in (node.left, node.right) if child]Java solution
import java.util.*;
public class Main {
static class Node {
long val;
Node left, right;
Node(long v) { val = v; }
}
// Build a tree from level order where -1 means "no node".
static Node readTree(Scanner sc) {
int k = sc.nextInt();
long[] v = new long[k];
for (int i = 0; i < k; i++) v[i] = sc.nextLong();
if (k == 0 || v[0] == -1) return null;
Node root = new Node(v[0]);
ArrayDeque<Node> q = new ArrayDeque<>();
q.add(root);
int i = 1;
while (!q.isEmpty() && i < k) {
Node cur = q.poll();
if (i < k && v[i] != -1) q.add(cur.left = new Node(v[i]));
i++;
if (i < k && v[i] != -1) q.add(cur.right = new Node(v[i]));
i++;
}
return root;
}
public static void main(String[] args) {
Node root = readTree(new Scanner(System.in));
ArrayDeque<Node> q = new ArrayDeque<>();
if (root != null) q.add(root);
StringBuilder sb = new StringBuilder();
while (!q.isEmpty()) {
int size = q.size();
for (int i = 0; i < size; i++) {
Node cur = q.poll();
sb.append(cur.val).append(i + 1 < size ? " " : "\n");
if (cur.left != null) q.add(cur.left);
if (cur.right != null) q.add(cur.right);
}
}
System.out.print(sb);
}
}