C Programs | IT Developer
IT Developer

C Programs

Share with a Friend
Previous
HOME
Next

Data Structures in C

Preorder Traversal in Binary Tree

Concept Overview

Preorder Traversal is a Depth-First Traversal (DFS) method.

Traversal Order:
      Root → Left → Right

Key Idea

  1. Visit the root node first.
  2. Recursively traverse the left subtree.
  3. Recursively traverse the right subtree.

 

C Program: Preorder Traversal in Binary Tree

Method 1: Recursive Preorder Traversal (Simple & Elegant)

C 
#include <stdio.h>


#include <stdlib.h>


 


// Structure for a tree node


struct Node {


    int data;


    struct Node *left, *right;


};


 


// Function to create a new node


struct Node* createNode(int value) {


    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));


    if (newNode == NULL) {


        printf("Memory allocation failed!\n");


        exit(1);


    }


    newNode->data = value;


    newNode->left = newNode->right = NULL;


    return newNode;


}


 


// Recursive Preorder Traversal (Root -> Left -> Right)


void preorderTraversal(struct Node* root) {


    if (root == NULL)


        return;


 


    printf("%d ", root->data);          // Visit root


    preorderTraversal(root->left);      // Traverse left subtree


    preorderTraversal(root->right);     // Traverse right subtree


}


 


int main() {


    /*


              1


             / \


            2   3


           / \


          4   5


    */


    struct Node* root = createNode(1);


    root->left = createNode(2);


    root->right = createNode(3);


    root->left->left = createNode(4);


    root->left->right = createNode(5);


 


    printf("Preorder Traversal (Recursive): ");


    preorderTraversal(root);


    printf("\n");


 


    return 0;


}

Output

 
OUTPUT :
Preorder Traversal (Recursive): 1 2 4 5 3

Step-by-Step Traversal Explanation

For the binary tree:

       1

      / \

     2   3

    / \

   4   5

Preorder Sequence (Root → Left → Right):
1 → 2 → 4 → 5 → 3

Output → 1 2 4 5 3

 

C Program: Preorder Traversal in Binary Tree

Method 2: Iterative Preorder Traversal (Using Stack)

While recursion is simpler, an iterative version is often preferred in production systems to avoid stack overflow or deep recursion issues.

C 
#include <stdio.h>


#include <stdlib.h>


 


// Binary Tree Node Structure


struct Node {


    int data;


    struct Node *left, *right;


};


 


// Stack Structure


struct Stack {


    int top;


    int capacity;


    struct Node **array;


};


 


// Function to create a new tree node


struct Node* createNode(int data) {


    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));


    newNode->data = data;


    newNode->left = newNode->right = NULL;


    return newNode;


}


 


// Function to create a stack


struct Stack* createStack(int capacity) {


    struct Stack* stack = (struct Stack*)malloc(sizeof(struct Stack));


    stack->top = -1;


    stack->capacity = capacity;


    stack->array = (struct Node**)malloc(capacity * sizeof(struct Node*));


    return stack;


}


 


// Stack utility functions


int isEmpty(struct Stack* stack) {


    return stack->top == -1;


}


 


void push(struct Stack* stack, struct Node* node) {


    stack->array[++stack->top] = node;


}


 


struct Node* pop(struct Stack* stack) {


    if (isEmpty(stack))


        return NULL;


    return stack->array[stack->top--];


}


 


// Iterative Preorder Traversal


void preorderTraversal(struct Node* root) {


    if (root == NULL)


        return;


 


    struct Stack* stack = createStack(100);


    push(stack, root);


 


    printf("Preorder Traversal (Iterative): ");


 


    while (!isEmpty(stack)) {


        struct Node* current = pop(stack);


        printf("%d ", current->data);


 


        // Push right child first so left is processed first


        if (current->right)


            push(stack, current->right);


        if (current->left)


            push(stack, current->left);


    }


    printf("\n");


}


 


// Main Function


int main() {


    /*


              1


             / \


            2   3


           / \


          4   5


    */


    struct Node* root = createNode(1);


    root->left = createNode(2);


    root->right = createNode(3);


    root->left->left = createNode(4);


    root->left->right = createNode(5);


 


    preorderTraversal(root);


 


    return 0;


}

Output

 
OUTPUT :
Preorder Traversal (Iterative): 1 2 4 5 3

Step-by-Step (Iterative) Process

Step

Stack (Top → Bottom)

Visited Node

Output

1

[1]

—

—

2

[]

1

1

3

[3,2]

—

1

4

[3]

2

1 2

5

[3,5,4]

—

1 2

6

[3,5]

4

1 2 4

7

[3]

5

1 2 4 5

8

[]

3

1 2 4 5 3

 Final Output: 1 2 4 5 3

Comparison: Recursive vs Iterative

Feature

Recursive

Iterative

Approach

Uses system call stack

Uses explicit stack

Ease of Implementation

Simpler

Slightly complex

Memory Usage

O(h), where h = tree height

O(n) (in stack)

Use Case

Small to medium trees

Large trees, iterative algorithms

 

Previous
Next