Inorder Tree Traversal in Binary Tree in C

Inorder Traversal in BST

Traversing in a tree can be done in many ways, one of which is inorder tree traversal. For quick mental calculation, you can remember the following –

Direction (Inorder)Clockwise
Rule

Left Center Right

(LCR)

How Inorder works (Manually)

  • The direction of traversal for inorder is anti-clockwise
  • Rule followed is LCR (Left-Center-Right)

This basically means, that we first try to visit bottommost, the left node then central node and then right and then move our way up to the tree.

Inorder Traversal in Binary Tree

Example

  • Leftmost node is 8, central node: 4, right node: 9 (Now, move up the tree)
    • Print 8 4 9
  • Leftmost node is 4 (already printed), central node: 2, right node: 5
    • Print 2 5
  • Whole left subtree is covered, print central node: 1 (Move to right subtree)
    • Print 1
  • (In right subtree) Leftmost element: NULL, central node: 6, right node: 10 (Move up the tree)
    • Print 6 10
  • Central node 3
    • Print 3
  • Leftmost node: 11, central 7, rightmost: 12
    • Print 11 7 12

Algorithm for Inorder Traversal

  • First, traverse the left sub-tree, (recursively call inorder(root -> left).
  • Visit and print the root node.
  • Traverse the right sub-tree, (recursively call inorder(root -> right).
// PrepInsta's program to do insertion in a Binary Search Tree (BST)
#include <stdio.h>
#include <stdlib.h>

// Basic struct of Tree
struct node
{
int val;
struct node *left, *right;
};

// Function to create a new Node
struct node* newNode(int item)
{
struct node* temp = (struct node *)malloc(sizeof(struct node));
temp->val = item;
temp->left = temp->right = NULL;
return temp;
}

// Function print the node in inorder format, when insertion is complete
void inorder(struct node* root)
{
if (root != NULL)
{
inorder(root->left);
printf("%d ", root->val);
inorder(root->right);
}
}

// Here we are finding where to insert the new node so BST is followed
struct node* insert(struct node* node, int val)
{
/* If the tree(subtree) is empty, return a new node by calling newNode func.*/
if (node == NULL) return newNode(val);

/* Else, we will do recursion down the tree to further subtrees */
if (val < node->val)
node->left = insert(node->left, val);
else if (val > node->val)
node->right = insert(node->right, val);

/* (Safety) return the node's pointer which is unchanged */
return node;
}

int main()
{
/* Our BST will look like this
100
/ \
90 140
/ \ / \
40 80 120 160 */
struct node* root = NULL;
root = insert(root, 100);
insert(root, 90);
insert(root, 40);
insert(root, 80);
insert(root, 140);
insert(root, 120);
insert(root, 160);

// Finally printing the tree using inorder
inorder(root);

return 0;
}

Output-

40 80 90 100 120 140 160
Inorder Tree Traversal of a BST
Quiz time

Fun Fact

What is Inorder Traversal used for ?

We generally use Inorder traversal technique on Binary Tress =, as it fetches the values from the underlying set in order. Using Post-order traversal is also an option, but during post order traversal while delete or freeing nodes it can even delete or free an entire binary tree, which is not a favorable condition, if you know what I mean.

Fun Fact for Inorder tree traveersal

One comment on “Inorder Tree Traversal in Binary Tree in C”