C Programs | IT Developer
IT Developer

C Programs

Share with a Friend
Previous
HOME
Next

Data Structures in C

Binary Search Tree Traversals

BST (Binary Search Tree) chapter with all three traversals — Inorder, Preorder, and Postorder — using a single BST structure.

These traversals are crucial for understanding tree structure, data order, and different processing sequences in tree-based algorithms.

 

Concept Overview

A Binary Search Tree (BST) is a hierarchical data structure that organizes data to allow efficient search, insertion, and deletion.

Tree traversals define the order in which nodes are visited.

There are three main depth-first traversals:

Traversal

Order

Description

Inorder

Left → Root → Right

Produces sorted order in BST

Preorder

Root → Left → Right

Useful for copying or serialization

Postorder

Left → Right → Root

Used for deletion and expression trees

 

C Program: Binary Search Tree Traversals

BST with All Traversals - Inorder, Preorder, Postorder

C 
#include <stdio.h>


#include <stdlib.h>


 


// Structure for a BST 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));


    newNode->data = value;


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


    return newNode;


}


 


// Function to insert a new node in BST


struct Node* insert(struct Node* root, int value) {


    if (root == NULL)


        return createNode(value);


 


    if (value < root->data)


        root->left = insert(root->left, value);


    else if (value > root->data)


        root->right = insert(root->right, value);


 


    return root;


}


 


// Inorder Traversal (Left -> Root -> Right)


void inorder(struct Node* root) {


    if (root != NULL) {


        inorder(root->left);


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


        inorder(root->right);


    }


}


 


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


void preorder(struct Node* root) {


    if (root != NULL) {


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


        preorder(root->left);


        preorder(root->right);


    }


}


 


// Postorder Traversal (Left -> Right -> Root)


void postorder(struct Node* root) {


    if (root != NULL) {


        postorder(root->left);


        postorder(root->right);


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


    }


}


 


int main() {


    struct Node* root = NULL;


 


    // Construct the BST


    root = insert(root, 50);


    root = insert(root, 30);


    root = insert(root, 70);


    root = insert(root, 20);


    root = insert(root, 40);


    root = insert(root, 60);


    root = insert(root, 80);


 


    printf("Binary Search Tree Traversals:\n");


 


    printf("Inorder Traversal   (Left -> Root -> Right): ");


    inorder(root);


    printf("\n");


 


    printf("Preorder Traversal  (Root -> Left -> Right): ");


    preorder(root);


    printf("\n");


 


    printf("Postorder Traversal (Left -> Right -> Root): ");


    postorder(root);


    printf("\n");


 


    return 0;


}

Output

 
OUTPUT :
Binary Search Tree Traversals:
Inorder Traversal   (Left -> Root -> Right): 20 30 40 50 60 70 80
Preorder Traversal  (Root -> Left -> Right): 50 30 20 40 70 60 80
Postorder Traversal (Left -> Right -> Root): 20 40 30 60 80 70 50

Visual Representation of the BST

After insertion, the BST structure is:

        50

       /  \

     30    70

    / \    / \

  20  40  60  80

 Step-by-Step Traversal Orders

Type

Node Visit Order

Output

Inorder

Left → Root → Right

20 30 40 50 60 70 80

Preorder

Root → Left → Right

50 30 20 40 70 60 80

Postorder

Left → Right → Root

20 40 30 60 80 70 50

 Traversal Use Cases

Traversal

Primary Use

Inorder

Produces sorted data from BST

Preorder

Used to copy or serialize a tree

Postorder

Used for deletion or evaluating expression trees

 Complexity Analysis

Operation

Time Complexity

Space Complexity

Inorder / Preorder / Postorder

O(n)

O(h), where h = height of tree

 Key Insights

  • Traversal algorithms are Depth-First Search (DFS) variants.
  • In BSTs, inorder traversal always gives ascending order of elements.
  • Preorder and Postorder are more about structural processing.

 

Previous
Next