Preorder Traversal

Visit the root before each subtree, producing root-left-right order.

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.

preorder Preorder records the current node before visiting left and right subtrees.

Basic Implementation

                            basic.c
                        
Replay: real traced execution (multi-file project)

                            #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");
}
void preorder(Node* node, int* output, int* n) { if (!node) return; output[(*n)++] = node->value; preorder(node->left, output, n); preorder(node->right, output, n); }
int main(void) { int output[7]; int n = 0; preorder(sample_tree(), output, &n); print_list(output, n); }

                        
1tree ← 4(2(1,3),6(5,7)), output ← []1#include <stdio.h>2#include <stdlib.h>⋯values this step4(2(1,3),6(5,7))tree[]output
2output ← [4]⋯26}27void preorder(Node* node, int* output, int* n) { if (!node) return; output[(*n)++] = node->value; preorder(node->left, output, n); preorder(node->right, output, n); }28int main(void) { int output[7]; int n = 0; preorder(sample_tree(), output, &n); print_list(output, n); }values this step[] → [4]output4node
3output ← [4, 2]⋯26}27void preorder(Node* node, int* output, int* n) { if (!node) return; output[(*n)++] = node->value; preorder(node->left, output, n); preorder(node->right, output, n); }28int main(void) { int output[7]; int n = 0; preorder(sample_tree(), output, &n); print_list(output, n); }values this step[4] → [4, 2]output2node
4output ← [4, 2, 1]⋯26}27void preorder(Node* node, int* output, int* n) { if (!node) return; output[(*n)++] = node->value; preorder(node->left, output, n); preorder(node->right, output, n); }28int main(void) { int output[7]; int n = 0; preorder(sample_tree(), output, &n); print_list(output, n); }values this step[4, 2] → [4, 2, 1]output1node
5output ← [4, 2, 1, 3]⋯26}27void preorder(Node* node, int* output, int* n) { if (!node) return; output[(*n)++] = node->value; preorder(node->left, output, n); preorder(node->right, output, n); }28int main(void) { int output[7]; int n = 0; preorder(sample_tree(), output, &n); print_list(output, n); }values this step[4, 2, 1] → [4, 2, 1, 3]output3node
6output ← [4, 2, 1, 3, 6]⋯26}27void preorder(Node* node, int* output, int* n) { if (!node) return; output[(*n)++] = node->value; preorder(node->left, output, n); preorder(node->right, output, n); }28int main(void) { int output[7]; int n = 0; preorder(sample_tree(), output, &n); print_list(output, n); }values this step[4, 2, 1, 3] → [4, 2, 1, 3, 6]output6node
7output ← [4, 2, 1, 3, 6, 5]⋯26}27void preorder(Node* node, int* output, int* n) { if (!node) return; output[(*n)++] = node->value; preorder(node->left, output, n); preorder(node->right, output, n); }28int main(void) { int output[7]; int n = 0; preorder(sample_tree(), output, &n); print_list(output, n); }values this step[4, 2, 1, 3, 6] → [4, 2, 1, 3, 6, 5]output5node
8output ← [4, 2, 1, 3, 6, 5, 7]⋯26}27void preorder(Node* node, int* output, int* n) { if (!node) return; output[(*n)++] = node->value; preorder(node->left, output, n); preorder(node->right, output, n); }28int main(void) { int output[7]; int n = 0; preorder(sample_tree(), output, &n); print_list(output, n); }values this step[4, 2, 1, 3, 6, 5] → [4, 2, 1, 3, 6, 5, 7]output7node
9sprintf(buf, "%d", node->value); append(out, buf);⋯12if (node == NULL) { append(out, "_"); return; }13sprintf(buf, "%d", node->value); append(out, buf);14if (node->left != NULL || node->right != NULL) {⋯values this step[4, 2, 1, 3, 6, 5, 7]output

Complexity

Time: O(n)
Space: O(h) recursion stack

Implementation notes

C uses typedef struct Node { int value; struct Node* left; struct Node* right; } Node, with raw child pointers that are either NULL or heap-allocated node addresses.
sample_tree() allocates the fixed seven-node tree with node_new; this checked executable does not free those nodes.
preorder(Node* node, int* output, int* n) stops immediately on NULL, then writes the current node before recursing left and right.
The output buffer is stack local int output[7]; n is a stack scalar passed by pointer, so output[(*n)++] = node->value mutates both the shared output array and the shared count across recursive frames.
The trace records visits in root-left-right order: 4, 2, 1, 3, 6, 5, 7, with output growing to [4, 2, 1, 3, 6, 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. Visible memory is heap nodes, recursive stack frames, the stack output array, and the shared count pointer.