Level-order traversal of a binary tree visits nodes from left to right across each depth level before moving deeper. This process aligns with breadth-first search (BFS) in graph theory, applied specifically to tree structures.

A queue is used as the supporting data structure because its first-in-first-out behavior naturally matches the need to process nodes level by level. In contrast, a stack supports depth-first strategies like recursion.

Implementation

The traversal collects values at each depth into separate sub-arrays, producing a two-dimensional array representing the tree layer by layer.

#include <vector>
#include <queue>
using namespace std;

struct Node {
    int value;
    Node* leftChild;
    Node* rightChild;
    Node(int v) : value(v), leftChild(nullptr), rightChild(nullptr) {}
    Node(int v, Node* lc, Node* rc) : value(v), leftChild(lc), rightChild(rc) {}
};

vector<vector<int>> traverseByLevel(Node* root) {
    vector<vector<int>> output;
    if (!root) return output;

    queue<Node*> pendingNodes;
    pendingNodes.push(root);

    while (!pendingNodes.empty()) {
        int levelCount = pendingNodes.size();
        vector<int> currentLayer;

        for (int step = 0; step < levelCount; ++step) {
            Node* current = pendingNodes.front();
            pendingNodes.pop();
            currentLayer.push_back(current->value);

            if (current->leftChild)
                pendingNodes.push(current->leftChild);
            if (current->rightChild)
                pendingNodes.push(current->rightChild);
        }
        output.push_back(currentLayer);
    }
    return output;
}

The key is fixing the iteration count per level (levelCount) based on the queue's initial size for that round. Using pendingNodes.size() directly inside the loop would yield incorrect results becuase the queue changes dynamically.

Reverse Level Order

To obtain levels from bottom to top, perform the same traversal and then reverse the container of level arrays.

#include <algorithm>

vector<vector<int>> traverseBottomUp(Node* root) {
    vector<vector<int>> layers = traverseByLevel(root);
    reverse(layers.begin(), layers.end());
    return layers;
}

Reversing the final collection produces a bottom-up view of the binary tree's structure.