Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

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

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

  1. Breadth-first search visits nodes level by level — use a queue.
  2. 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);
    }
}

Solve Level Order Traversal online · All practice problems