Binary Tree Traversals (Static)

1. In-order Traversal

Important Note: Dear Students, do not get confused. When you refer to binary tree traversal, it applies to any type of binary tree, BST too.

The in-order traversal visits the left child, then the current node, and finally the right child. In array representation:

The root is at index 0.
The left child of a node at index i is at index 2*i + 1.
The right child of a node at index i is at index 2*i + 2.

Program in C

#define MAX_SIZE 15 // Maximum size of the binary tree array

int tree[MAX_SIZE]; // Array to represent the binary tree

// Function to perform in-order traversal of the binary tree
void inorderTraversal(int index) {
    // If the index is out of bounds or the node is empty, return
    if (index >= MAX_SIZE || tree[index] == -1) {
        return;
    }

    // Traverse the left subtree (left child is at 2 * index + 1)
    inorderTraversal(2 * index + 1);

    // Visit the current node (print its value)
    printf("%d ", tree[index]);

    // Traverse the right subtree (right child is at 2 * index + 2)
    inorderTraversal(2 * index + 2);
}

int main() {
    // Initialize all elements to -1 (indicating empty nodes)
    for (int i = 0; i < MAX_SIZE; i++) {
        tree[i] = -1;
    }

    // Manually insert values into the binary tree array (in level-order)
    tree[0] = 1;  // Root node
    tree[1] = 2;  // Left child of root
    tree[2] = 3;  // Right child of root
    tree[3] = 4;  // Left child of node 2
    tree[4] = 5;  // Right child of node 2
    tree[5] = 6;  // Left child of node 3
    tree[6] = 7;  // Right child of node 3

    // Perform in-order traversal and display the tree
    printf("In-order Traversal of the Binary Tree:\n");
    inorderTraversal(0); // Start traversal from the root (index 0)

    return 0; // End of program
}

Tree Representation in Array:
- The tree is represented as an array tree[] where:
  - tree[0] is the root.
  - tree[2*i + 1] is the left child of node at index i.
  - tree[2*i + 2] is the right child of node at index i.
In-order Traversal:
- The inorderTraversal(int index) function is used to perform the in-order traversal:
  - It first recursively calls itself to visit the left child (2*i + 1).
  - Then, it prints the value of the node.
  - Finally, it recursively calls itself to visit the right child (2*i + 2).

2. Pre-order Traversal

In pre-order traversal, the root node is visited first, followed by the left child, and then the right child. For an array representation:

The root is at index 0.
The left child of a node at index i is at index 2*i + 1.
The right child of a node at index i is at index 2*i + 2.

Program in C

#define MAX_SIZE 15 // Maximum size of the binary tree array

int tree[MAX_SIZE]; // Array to represent the binary tree

// Function to perform pre-order traversal of the binary tree
void preorderTraversal(int index) {
    // If the index is out of bounds or the node is empty, return
    if (index >= MAX_SIZE || tree[index] == -1) {
        return;
    }

    // Visit the current node (print its value)
    printf("%d ", tree[index]);

    // Traverse the left subtree (left child is at 2 * index + 1)
    preorderTraversal(2 * index + 1);

    // Traverse the right subtree (right child is at 2 * index + 2)
    preorderTraversal(2 * index + 2);
}

int main() {
    // Initialize all elements to -1 (indicating empty nodes)
    for (int i = 0; i < MAX_SIZE; i++) {
        tree[i] = -1;
    }

    // Manually insert values into the binary tree array (in level-order)
    tree[0] = 1;  // Root node
    tree[1] = 2;  // Left child of root
    tree[2] = 3;  // Right child of root
    tree[3] = 4;  // Left child of node 2
    tree[4] = 5;  // Right child of node 2
    tree[5] = 6;  // Left child of node 3
    tree[6] = 7;  // Right child of node 3

    // Perform pre-order traversal and display the tree
    printf("Pre-order Traversal of the Binary Tree:\n");
    preorderTraversal(0); // Start traversal from the root (index 0)

    return 0; // End of program
}

Tree Representation in Array:
- The tree is represented as an array tree[] where:
  - tree[0] is the root.
  - tree[2*i + 1] is the left child of the node at index i.
  - tree[2*i + 2] is the right child of the node at index i.
Pre-order Traversal:
- The preorderTraversal(int index) function follows the pre-order traversal:
  - Visit the current node and print its value.
  - Recursively traverse the left subtree (2*i + 1).
  - Recursively traverse the right subtree (2*i + 2).

3. Post-order Traversal

In post-order traversal, the left child is visited first, followed by the right child, and then the root node. In array representation:

The root is at index 0.
The left child of a node at index i is at index 2*i + 1.
The right child of a node at index i is at index 2*i + 2.

Program in C

#define MAX_SIZE 15 // Maximum size of the binary tree array

int tree[MAX_SIZE]; // Array to represent the binary tree

// Function to perform post-order traversal of the binary tree
void postorderTraversal(int index) {
    // If the index is out of bounds or the node is empty, return
    if (index >= MAX_SIZE || tree[index] == -1) {
        return;
    }

    // Traverse the left subtree (left child is at 2 * index + 1)
    postorderTraversal(2 * index + 1);

    // Traverse the right subtree (right child is at 2 * index + 2)
    postorderTraversal(2 * index + 2);

    // Visit the current node (print its value)
    printf("%d ", tree[index]);
}

int main() {
    // Initialize all elements to -1 (indicating empty nodes)
    for (int i = 0; i < MAX_SIZE; i++) {
        tree[i] = -1;
    }

    // Manually insert values into the binary tree array (in level-order)
    tree[0] = 1;  // Root node
    tree[1] = 2;  // Left child of root
    tree[2] = 3;  // Right child of root
    tree[3] = 4;  // Left child of node 2
    tree[4] = 5;  // Right child of node 2
    tree[5] = 6;  // Left child of node 3
    tree[6] = 7;  // Right child of node 3

    // Perform post-order traversal and display the tree
    printf("Post-order Traversal of the Binary Tree:\n");
    postorderTraversal(0); // Start traversal from the root (index 0)

    return 0; // End of program
}

Tree Representation in Array:
- The tree is represented as an array tree[] where:
  - tree[0] is the root.
  - tree[2*i + 1] is the left child of the node at index i.
  - tree[2*i + 2] is the right child of the node at index i.
Post-order Traversal:
- The postorderTraversal(int index) function follows the post-order traversal:
  - Recursively traverse the left subtree (2*i + 1).
  - Recursively traverse the right subtree (2*i + 2).
  - Visit the current node and print its value.