Binary Tree Traversal Orders

Tree traversal visits all nodes in a binary tree in a specific hierarchical order:

1. Inorder ($Left → Root → Right$): Yields elements in ascending sorted order for Binary Search Trees.
2. Preorder ($Root → Left → Right$): Used for serializing/copying trees.
3. Postorder ($Left → Right → Root$): Used for bottom-up node deletion.

---

C Source Code

c (ISO Standard)
Run in Compiler.cCopy
#include <stdio.h>
#include <stdlib.h>

typedef struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
} TreeNode;

TreeNode* createNode(int value) {
    TreeNode *node = (TreeNode*)malloc(sizeof(TreeNode));
    node->val = value;
    node->left = NULL;
    node->right = NULL;
    return node;
}

void inorder(const TreeNode *root) {
    if (root == NULL) return;
    inorder(root->left);
    printf("%d ", root->val);
    inorder(root->right);
}

void preorder(const TreeNode *root) {
    if (root == NULL) return;
    printf("%d ", root->val);
    preorder(root->left);
    preorder(root->right);
}

void postorder(const TreeNode *root) {
    if (root == NULL) return;
    postorder(root->left);
    postorder(root->right);
    printf("%d ", root->val);
}

int main() {
    /* Construct Tree:
            1
           / \
          2   3
         / \
        4   5
    */
    TreeNode *root = createNode(1);
    root->left = createNode(2);
    root->right = createNode(3);
    root->left->left = createNode(4);
    root->left->right = createNode(5);

    printf("Inorder Traversal:   ");
    inorder(root);
    printf("\nPreorder Traversal:  ");
    preorder(root);
    printf("\nPostorder Traversal: ");
    postorder(root);
    printf("\n");

    return 0;
}

Sample Output

text (ISO Standard)
Copy
Inorder Traversal:   4 2 5 1 3 
Preorder Traversal:  1 2 4 5 3 
Postorder Traversal: 4 5 2 3 1 

---

Complexity Analysis

• Time Complexity: O(n) where each node is visited once.
• Space Complexity: O(h) where h is tree height (stack recursion depth).

---

Related Data Structures

• Linear dynamic nodes in Singly Linked List in C.
• Binary partition searching in Binary Search in C.