Program for Binary Tree Traversals (Inorder, Preorder and Postorder)
#include <stdio.h>
#include <stdlib.h>
/* A binary tree node has data, pointer to left child and a pointer to right child */
struct node {
int data;
struct node* left;
struct node* right;
};
/* Helper function that allocates a new node with the given data and NULL left and right
pointers. */
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);
}
/* Given a binary tree, print its nodes according to the “bottom-up" postorder traversal. */
void printPostorder(struct node* node) {
if (node = = NULL)
return;
// first recur on left subtree
printPostorder(node->left);
// then recur on right subtree
printPostorder(node->right);
// now deal with the node
printf("%d ", node->data);
}
/* Given a binary tree, print its nodes in inorder*/
void printInorder(struct node* node) {
if (node = = NULL)
return;
/* first recur on left child */
printInorder(node->left);
/* then print the data of node */
printf("%d ", node->data);
/* now recur on right child */
printInorder(node->right);
}
/* Given a binary tree, print its nodes in inorder*/
void printPreorder(struct node* node) {
if (node = = NULL)
return;
/* first print data of node */
printf("%d ", node->data);
/* then recur on left sutree */
printPreorder(node->left);
/* now recur on right subtree */
printPreorder(node->right);
}
/* Driver program to test above functions*/
int main() {
struct node *root = newNode(1);
root->left = newNode(2);
root->right = newNode(3);
root->left->left = newNode(4);
root->left->right = newNode(5);
printf("\n Preorder traversal of binary tree is \n");
printPreorder(root);
printf("\n Inorder traversal of binary tree is \n");
printInorder(root);
printf("\n Postorder traversal of binary tree is \n");
printPostorder(root);
getchar();
return 0;
}
Output:
$ gcc PreorderRecursive.c
$ ./a.out
Preorder traversal of binary tree is
12453
Inorder traversal of binary tree is
42513
Postorder traversal of binary tree is
45231
Binary Tree Traversals with Runtime Input
#include <stdio.h>
#include <stdlib.h>
// Define structure for tree node
struct Node {
int data;
struct Node* left;
struct Node* right;
};
// Create a new node
struct Node* createNode(int data) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = data;
newNode->left = newNode->right = NULL;
return newNode;
}
// Insert node (basic insert for binary tree, not BST)
struct Node* insert(struct Node* root, int data) {
if (root == NULL) {
return createNode(data);
}
char direction;
printf("Insert %d to the left or right of %d? (l/r): ", data, root->data);
scanf(" %c", &direction);
if (direction == 'l' || direction == 'L') {
root->left = insert(root->left, data);
} else {
root->right = insert(root->right, data);
}
return root;
}
// Inorder Traversal (Left, Root, Right)
void inorder(struct Node* root) {
if (root != NULL) {
inorder(root->left);
printf("%d ", root->data);
inorder(root->right);
}
}
// Preorder Traversal (Root, Left, Right)
void preorder(struct Node* root) {
if (root != NULL) {
printf("%d ", root->data);
preorder(root->left);
preorder(root->right);
}
}
// Postorder Traversal (Left, Right, Root)
void postorder(struct Node* root) {
if (root != NULL) {
postorder(root->left);
postorder(root->right);
printf("%d ", root->data);
}
}
int main() {
struct Node* root = NULL;
int n, value;
printf("Enter number of nodes: ");
scanf("%d", &n);
if (n <= 0) {
printf("No nodes to insert.\n");
return 0;
}
printf("Enter value for root node: ");
scanf("%d", &value);
root = insert(root, value);
for (int i = 1; i < n; i++) {
printf("Enter value for node %d: ", i + 1);
scanf("%d", &value);
insert(root, value);
}
printf("\nInorder Traversal: ");
inorder(root);
printf("\nPreorder Traversal: ");
preorder(root);
printf("\nPostorder Traversal: ");
postorder(root);
printf("\n");
return 0;
}
Output:
Enter number of nodes: 3
Enter value for root node: 6
Enter value for node 2: 3
Insert 3 to the left or right of 6? (l/r): l
Enter value for node 3: 8
Insert 8 to the left or right of 6? (l/r): r
Inorder Traversal: 3 6 8
Preorder Traversal: 6 3 8
Postorder Traversal: 3 8 6
Enter number of nodes: 3
Enter value for root node: 10
Enter value for node 2: 5
Insert 5 to the left or right of 10? (l/r): l
Enter value for node 3: 15
Insert 15 to the left or right of 10? (l/r): r
Inorder Traversal: 5 10 15
Preorder Traversal: 10 5 15
Postorder Traversal: 5 15 10
