C Program for Preorder Traversal of Binary Tree

A C program for preorder traversal uses a recursive function that first prints the current node's value, then recursively visits the left subtree, and finally the right subtree, like void preorder(Node* root) { if(root) { printf("%d ", root->data); preorder(root->left); preorder(root->right); } }.

Examples

InputTree: 1 (root), 2 (left child), 3 (right child)

Output1 2 3

InputTree: 10 (root), 20 (left child), 30 (right child), 40 (left of 20)

Output10 20 40 30

InputEmpty tree (root is NULL)

Output

How to Think About It

To do preorder traversal, think like visiting a family tree: first, you meet the parent (root), then you visit the left child and all its descendants, and finally the right child and its descendants. You do this by checking if the current node exists, printing its value, then calling the same process on the left and right children.

Algorithm

1

Start at the root node.

2

If the current node is not null, print its value.

3

Recursively perform preorder traversal on the left child.

4

Recursively perform preorder traversal on the right child.

5

Stop when all nodes are visited.

Code

c

#include <stdio.h>
#include <stdlib.h>

typedef struct Node {
    int data;
    struct Node* left;
    struct Node* right;
} Node;

Node* newNode(int data) {
    Node* node = (Node*)malloc(sizeof(Node));
    node->data = data;
    node->left = NULL;
    node->right = NULL;
    return node;
}

void preorder(Node* root) {
    if (root) {
        printf("%d ", root->data);
        preorder(root->left);
        preorder(root->right);
    }
}

int main() {
    Node* root = newNode(1);
    root->left = newNode(2);
    root->right = newNode(3);

    preorder(root);
    return 0;
}

Output

1 2 3 

Dry Run

Let's trace preorder traversal on a tree with root 1, left child 2, and right child 3.

1

Visit root node

Current node = 1; print 1

2

Traverse left subtree

Current node = 2; print 2

3

Left child of 2 is NULL

Return to node 1

4

Traverse right subtree

Current node = 3; print 3

5

Left and right children of 3 are NULL

Traversal complete

Step	Node Visited	Output So Far
1	1	1
2	2	1 2
3	NULL	1 2
4	3	1 2 3
5	NULL	1 2 3

Why This Works

Step 1: Visit current node first

Preorder means you handle the current node before its children, so you print the node's data immediately.

Step 2: Traverse left subtree

After printing, you move to the left child and repeat the process recursively.

Step 3: Traverse right subtree

Once the left subtree is done, you do the same for the right child, ensuring all nodes are visited.

Alternative Approaches

Iterative Preorder Traversal using Stack

c

#include <stdio.h>
#include <stdlib.h>

typedef struct Node {
    int data;
    struct Node* left;
    struct Node* right;
} Node;

Node* newNode(int data) {
    Node* node = (Node*)malloc(sizeof(Node));
    node->data = data;
    node->left = NULL;
    node->right = NULL;
    return node;
}

typedef struct Stack {
    Node* nodes[100];
    int top;
} Stack;

void push(Stack* s, Node* node) {
    s->nodes[++(s->top)] = node;
}

Node* pop(Stack* s) {
    return s->nodes[(s->top)--];
}

int isEmpty(Stack* s) {
    return s->top == -1;
}

void preorderIterative(Node* root) {
    if (!root) return;
    Stack s;
    s.top = -1;
    push(&s, root);

    while (!isEmpty(&s)) {
        Node* curr = pop(&s);
        printf("%d ", curr->data);
        if (curr->right) push(&s, curr->right);
        if (curr->left) push(&s, curr->left);
    }
}

int main() {
    Node* root = newNode(1);
    root->left = newNode(2);
    root->right = newNode(3);

    preorderIterative(root);
    return 0;
}

This method avoids recursion by using a stack, which can be better for very deep trees to prevent stack overflow.

Complexity: O(n) time, O(h) space

Time Complexity

Each node is visited exactly once, so the time complexity is O(n), where n is the number of nodes.

Space Complexity

The space depends on the recursion stack or explicit stack size, which is O(h), where h is the tree height.

Which Approach is Fastest?

Both recursive and iterative methods have the same time complexity; iterative avoids recursion overhead but uses explicit stack.

Approach	Time	Space	Best For
Recursive Preorder	O(n)	O(h)	Simple code, small to medium trees
Iterative Preorder	O(n)	O(h)	Very deep trees, avoid recursion limits