Binary Trees

Simulation Speed:1x

Tree Traversal

Tree traversal is the process of visiting each node in a tree exactly once. The order in which we visit nodes defines the traversal type. Each method serves different purposes in data processing and algorithm implementation.

Inorder (Left → Root → Right)

Visit order:

Traverse left subtree
Visit root node
Traverse right subtree

Results in sorted order for BSTs. Commonly used when you need nodes in ascending order.

Preorder (Root → Left → Right)

Visit order:

Visit root node
Traverse left subtree
Traverse right subtree

Useful for creating a copy of the tree or getting prefix expression of an expression tree.

Postorder (Left → Right → Root)

Visit order:

Traverse left subtree
Traverse right subtree
Visit root node

Used in deletion operations and evaluating postfix expressions. Children processed before parent.

Example Results for Tree Below:

Inorder:

20 → 30 → 60 → 50 → 70 → 80

Preorder:

50 → 30 → 20 → 60 → 70 → 80

Postorder:

20 → 60 → 30 → 80 → 70 → 50

Operations Log:

C Code Example:

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

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

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

void inorderTraversal(struct Node* root) {
    if (root != NULL) {
        inorderTraversal(root->left);
        printf("%d ", root->data);
        inorderTraversal(root->right);
    }
}

void preorderTraversal(struct Node* root) {
    if (root != NULL) {
        printf("%d ", root->data);
        preorderTraversal(root->left);
        preorderTraversal(root->right);
    }
}

void postorderTraversal(struct Node* root) {
    if (root != NULL) {
        postorderTraversal(root->left);
        postorderTraversal(root->right);
        printf("%d ", root->data);
    }
}

int main() {
    struct Node* root = newNode(50);
    root->left = newNode(30);
    root->right = newNode(70);
    root->left->left = newNode(20);
    root->left->right = newNode(60);
    root->right->left = NULL;
    root->right->right = newNode(80);

    printf("Inorder traversal: ");
    inorderTraversal(root);
    printf("\n");

    printf("Preorder traversal: ");
    preorderTraversal(root);
    printf("\n");

    printf("Postorder traversal: ");
    postorderTraversal(root);
    printf("\n");

    return 0;
}