Trees

Level-Order Traversal

Visit a tree breadth-first with a queue.

Algorithm

The canonical tree is 4(2(1,3),6(5,7)), so this C++ DSA implementation can be compared directly with the rest of the DSA track.

Basic Implementation

basic.cpp 
#include <iostream>
#include <queue>
#include <sstream>
#include <string>
#include <vector>
using namespace std;
struct Node { int value; Node* left; Node* right; Node(int v, Node* l=nullptr, Node* r=nullptr): value(v), left(l), right(r) {} };
string render(Node* node) {
    if (node == nullptr) return "_";
    if (node->left == nullptr && node->right == nullptr) return to_string(node->value);
    return to_string(node->value) + "(" + render(node->left) + "," + render(node->right) + ")";
}
Node* sampleTree() {
    return new Node(4, new Node(2, new Node(1), new Node(3)), new Node(6, new Node(5), new Node(7)));
}
string listString(const vector<int>& values) {
    stringstream out; out << "[";
    for (size_t i = 0; i < values.size(); i++) { if (i) out << ", "; out << values[i]; }
    out << "]"; return out.str();
}
int main() { queue<Node*> q; q.push(sampleTree()); vector<int> output; while (!q.empty()) { Node* node = q.front(); q.pop(); output.push_back(node->value); if (node->left) q.push(node->left); if (node->right) q.push(node->right); } cout << listString(output) << "\n"; }

Complexity

  • Time: O(n)
  • Space: O(w) queue space

Implementation notes

  • In C++, nodes are struct Node objects connected by raw Node* left and Node* right links; sampleTree() allocates them with nested new Node(...) calls.
  • The traversal queue is std::queue<Node*>, storing non-owning raw pointers to already allocated nodes rather than node values or copies.
  • The loop guard is while (!q.empty()); each step reads Node* node = q.front(), calls q.pop(), appends node->value to std::vector<int> output, then enqueues non-null children with q.push(node->left/right).
  • The trace records queue states [4], [2, 6], [6, 1, 3], [1, 3, 5, 7], and finally [], while output grows to [4, 2, 6, 1, 3, 5, 7].
  • listString(const std::vector<int>&) uses std::stringstream and a size_t loop to format the output, then std::cout << ... << "\n" prints [4, 2, 6, 1, 3, 5, 7].
  • Visible allocation is the tree nodes, queue adapter storage, output vector, and formatting buffer. The source uses raw pointers and does not show a matching delete cleanup path.
level order Level-order traversal uses a queue to visit shallower nodes first.