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

#include <stdio.h>

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

int tree[MAX_SIZE] = {-1}; // Array to store the binary tree, initialized to -1 (empty)

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
inorderTraversal(2 * index + 1);

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

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

int main() {
// Manually insert values in 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 from the root (index 0)

return 0;
}

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

#include <stdio.h>

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

int tree[MAX_SIZE] = {-1}; // Array to store the binary tree, initialized to -1 (empty)

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
preorderTraversal(2 * index + 1);

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

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

return 0;
}

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

#include <stdio.h>

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

int tree[MAX_SIZE] = {-1}; // Array to store the binary tree, initialized to -1 (empty)

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
postorderTraversal(2 * index + 1);

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

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

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

return 0;
}

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.