Binary Tree Traversal

Binary Tree Traversal is the process of visiting each node in a binary tree exactly once in a specific order.

Traversals help in accessing, printing, modifying, or analyzing data in the tree.

There are two main categories of traversal

Depth-First Traversal (DFT)
Breadth-First Traversal (BFT)

1. Depth-First Traversal

In DFT, we explore as far as possible along each branch before backtracking. There are three types

a) Inorder Traversal

In inorder traversal, the nodes are visited in the left-root-right order. It means we first traverse the left sub-tree, then the root node, and finally the right sub-tree.

This traversal is particularly useful for binary search trees, as it retrieves the nodes in sorted ascending order.

Process of Inorder Traversal:

Traverse the left sub-tree recursively.
Visit the root node.
Traverse the right sub-tree recursively.

Example Tree:

      40
     /  \
   20    60
  / \    / \
10 30  50  70

Inorder Traversal: 10 20 30 40 50 60 70

b) Preorder Traversal

In preorder traversal, the nodes are visited in the root-left-right order. We first visit the root, then recursively traverse the left sub-tree, followed by the right sub-tree.

This traversal is commonly used to create a copy of a tree or to serialize a tree structure.

Process of Preorder Traversal:

Visit the root node.
Traverse the left sub-tree recursively.
Traverse the right sub-tree recursively.

Preorder Traversal: 40 20 10 30 60 50 70

c) Postorder Traversal

In postorder traversal, the nodes are visited in the left-right-root order. First, we visit the left and right sub-trees recursively, and finally process the root node.

This traversal is used in scenarios like deleting a tree or evaluating arithmetic expressions in an expression tree.

Process of Postorder Traversal:

Traverse the left sub-tree recursively.
Traverse the right sub-tree recursively.
Visit the root node.

Postorder Traversal: 10 30 20 50 70 60 40

2. Level Order (BFT)

Also known as Breadth-First Traversal, level-order traversal visits all nodes level by level from top to bottom and left to right at each level. It uses a queue data structure to keep track of nodes at each level.

This traversal is ideal when you want to visualize the tree structure or perform operations level-wise.

Process of Level-Order Traversal:-

Enqueue the root node.
While the queue is not empty:
- Dequeue a node and visit it.
- Enqueue the left child if it exists.
- Enqueue the right child if it exists.

Level-Order Traversal: 40 20 60 10 30 50 70

Summary Table

Traversal Type	Visiting Order	Use Case
Inorder	Left → Root → Right	Get sorted data (BST)
Preorder	Root → Left → Right	Clone / Copy tree
Postorder	Left → Right → Root	Delete tree, Expression evaluation
Level-order	Level by level (Top → Down)	Visual representation, BFS logic

Example of Sample Binary Tree Traversal

We’ll use the following binary tree for all traversal examples.

         40
        /  \
      20    60
     / \    / \
   10  30  50  70

Inorder Traversal

Steps: (Left → Root → Right)

Go to left sub-tree of 40 → go to 20
Go to left of 20 → 10 (leftmost node)
Visit 10 → back to 20
Visit 20 → go to 30
Visit 30 → back to 40
Visit 40 → go to right 60
Go to left of 60 → 50 → visit
Visit 60 → go to 70 → visit

Inorder Output: 10 20 30 40 50 60 70

Preorder Traversal

Steps: (Root → Left → Right)

Visit root 40
Go to left → visit 20
Left of 20 → visit 10
Back to 20 → right → visit 30
Back to 40 → right → visit 60
Left of 60 → visit 50
Right of 60 → visit 70

Preorder Output: 40 20 10 30 60 50 70

Postorder Traversal

Steps: (Left → Right → Root)

Left sub-tree of 40 → 20
Left of 20 → 10 → visit
Right of 20 → 30 → visit
Visit 20
Right sub-tree of 40 → 60
Left of 60 → 50 → visit
Right of 60 → 70 → visit
Visit 60
Finally, visit root 40

Postorder Output: 10 30 20 50 70 60 40

Level Order Traversal

Steps: (Top to Bottom, Left to Right - Using Queue):

Enqueue root → 40
Dequeue 40 → visit
Enqueue 20 and 60
Dequeue 20 → visit → enqueue 10 and 30
Dequeue 60 → visit → enqueue 50 and 70
Visit remaining nodes: 10, 30, 50, 70

Level Order Output: 40 20 60 10 30 50 70

C Program: Binary Tree Traversals

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

// Define the structure of a node
struct Node {
    int data;
    struct Node* left;
    struct Node* right;
};

// 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;
}

// Inorder Traversal (Left - Root - Right)
void inorder(struct Node* root) {
    if (root == NULL) return;
    inorder(root->left);
    printf("%d ", root->data);
    inorder(root->right);
}

// Preorder Traversal (Root - Left - Right)
void preorder(struct Node* root) {
    if (root == NULL) return;
    printf("%d ", root->data);
    preorder(root->left);
    preorder(root->right);
}

// Postorder Traversal (Left - Right - Root)
void postorder(struct Node* root) {
    if (root == NULL) return;
    postorder(root->left);
    postorder(root->right);
    printf("%d ", root->data);
}

// Queue structure for level order traversal
#define MAX 100
struct Node* queue[MAX];
int front = -1, rear = -1;

void enqueue(struct Node* root) {
    if (rear == MAX - 1)
        return;
    queue[++rear] = root;
    if (front == -1)
        front = 0;
}

struct Node* dequeue() {
    if (front == -1 || front > rear)
        return NULL;
    return queue[front++];
}

// Level Order Traversal
void levelOrder(struct Node* root) {
    if (root == NULL) return;

    enqueue(root);

    while (front <= rear) {
        struct Node* current = dequeue();
        printf("%d ", current->data);

        if (current->left != NULL)
            enqueue(current->left);
        if (current->right != NULL)
            enqueue(current->right);
    }
}

// Main function to test traversals
int main() {
    // Creating the example binary tree:
    /*
             40
            /  \
          20    60
         / \    / \
       10  30  50  70
    */
    struct Node* root = createNode(40);
    root->left = createNode(20);
    root->right = createNode(60);
    root->left->left = createNode(10);
    root->left->right = createNode(30);
    root->right->left = createNode(50);
    root->right->right = createNode(70);

    printf("Inorder Traversal: ");
    inorder(root);
    printf("\n");

    printf("Preorder Traversal: ");
    preorder(root);
    printf("\n");

    printf("Postorder Traversal: ");
    postorder(root);
    printf("\n");

    printf("Level Order Traversal: ");
    levelOrder(root);
    printf("\n");

    return 0;
}

Output (for the given tree)

Inorder Traversal: 10 20 30 40 50 60 70 
Preorder Traversal: 40 20 10 30 60 50 70 
Postorder Traversal: 10 30 20 50 70 60 40 
Level Order Traversal: 40 20 60 10 30 50 70

Menu