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.c

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct Node { int value; struct Node* left; struct Node* right; } Node;
Node* node_new(int value, Node* left, Node* right) {
    Node* node = (Node*)malloc(sizeof(Node));
    node->value = value; node->left = left; node->right = right; return node;
}
void append(char* out, const char* text) { strcat(out, text); }
void render(Node* node, char* out) {
    char buf[16];
    if (node == NULL) { append(out, "_"); return; }
    sprintf(buf, "%d", node->value); append(out, buf);
    if (node->left != NULL || node->right != NULL) {
        append(out, "("); render(node->left, out); append(out, ","); render(node->right, out); append(out, ")");
    }
}
Node* sample_tree(void) {
    return node_new(4, node_new(2, node_new(1, NULL, NULL), node_new(3, NULL, NULL)),
                       node_new(6, node_new(5, NULL, NULL), node_new(7, NULL, NULL)));
}
void print_list(int* values, int n) {
    printf("[");
    for (int i = 0; i < n; i++) { if (i) printf(", "); printf("%d", values[i]); }
    printf("]\n");
}
int main(void) { Node* queue[8]; int front = 0, back = 0; int output[7], n = 0; queue[back++] = sample_tree(); while (front < back) { Node* node = queue[front++]; output[n++] = node->value; if (node->left) queue[back++] = node->left; if (node->right) queue[back++] = node->right; } print_list(output, n); }

Complexity

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

Implementation notes

C uses the same Node layout as the tree-build lesson: int value plus raw left and right child pointers that are either NULL or heap node addresses from malloc.
sample_tree() allocates the fixed seven-node tree with node_new; this checked executable does not free those nodes.
The level-order queue is a stack local Node* queue[8] plus scalar indexes front and back, not a ring buffer or heap-allocated queue object.
Enqueue writes node pointers with queue[back++] = ...; dequeue reads Node* node = queue[front++]. Child links are tested for non-NULL before their pointers are appended.
Values are copied into stack array int output[7] with output[n++] = node->value; the tree nodes and child pointers are read but not mutated.
The trace records queue states [4], [2, 6], [6, 1, 3], [1, 3, 5, 7], [3, 5, 7], [5, 7], [7], and [], while output grows to [4, 2, 6, 1, 3, 5, 7].
print_list(int* values, int n) receives the output array as a pointer after parameter decay and prints comma-separated integers with printf.

level order Level-order traversal uses a queue to visit shallower nodes first.