Trees

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.

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");
}
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); }

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.
preorder Preorder records the current node before visiting left and right subtrees.