Inorder Tree Traversal in Binary Tree in C

Inorder Traversal in BST

Traversing in a tree can be done in many ways, on this page we will discuss about Inorder Tree Traversal in Binary Tree in C . For quick mental calculation, you can remember the following –
Direction (Inorder) Clockwise
Rule Left Center Right (LCR)

Inorder Tree Traversal in Binary Tree in C Language

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 Tree Traversal in Binary Tree in C

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).

Run

// Program for tree traversal inorder in Binary Tree
#include<stdio.h>
#include<stdlib.h>

// We are creating struct for the binary tree below
struct node
{
  int data;
  struct node *left, *right;
};

// newNode function for initialisation of the newly created node
struct node *newNode (int item)
{
  struct node *temporary = (struct node *) malloc (sizeof (struct node));
  temporary->data = item;
  temporary->left = temporary->right = NULL;
  return temporary;
}

// Here we print the inorder recursively
void inorder (struct node *root)
{
  if (root != NULL)
    {
      inorder (root->left);
      printf ("%d ", root->data);
      inorder (root->right);
    }
}

// Basic Program to insert new node at the correct position in BST
struct node *insert (struct node *node, int data)
{
  /* When there no node in the tree(subtree) then create 
   and return new node using newNode function */
  if (node == NULL)
    return newNode (data);

  /* If not then we recur down the tree to find correct position for insertion */
  if (data < node->data)
    node->left = insert (node->left, data);
  else if (data > node->data)
    node->right = insert (node->right, data);

  return node;
}

int main ()
{
  /* What our binary search tree looks like really 
      9 
     / \ 
    7  14
   / \ / \ 
  5  8 11 16 */
  
  struct node *root = NULL;
  root = insert (root, 9);
  insert (root, 7);
  insert (root, 5);
  insert (root, 8);
  insert (root, 14);
  insert (root, 11);
  insert (root, 16);


  printf ("The inorder is :\n");
  inorder (root);

  return 0;
}

Output:

The inorder is :
5 7 8 9 11 14 16

Prime Course Trailer

Related Banners

Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription

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

Get over 200+ course One Subscription

Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others

Checkout list of all the video courses in PrepInsta Prime Subscription

Checkout list of all the video courses in PrepInsta Prime Subscription

Introduction to Trees

Binary Trees

Binary Search Trees

Traversals

  • Traversal in Trees
  • Tree Traversals: Breadth-First Search (BFS) : C | C++ | Java
  • Tree Traversals: Depth First Search (DFS) : C | C++ | Java
  • Construct a Binary Tree from Postorder and Inorder

B – Trees

AVL Trees

  • AVL Trees
    • AVL Trees: Introduction
    • AVL Tree Insertion : C | C++ | Java
    • AVL Tree Deletion : C | C++ | Java
    • Insertion in a Binary Tree (Level Order) – C | C++ | Java
    • Searching in Binary Tree – C | C++ | Java
    • Searching in a Binary Search Tree – C | C++ | Java

Complete Programs for Trees

  • Depth First Traversals – C | C++ | Java
  • Level Order Traversal – C | C++Java
  • Construct Tree from given Inorder and Preorder traversals – C | C++Java
  • Construct Tree from given Postorder and Inorder traversals – C | C++Java
  • Construct Tree from given Postorder and Preorder traversal – C | C++Java
  • Find size of the Binary tree – C | C++Java
  • Find the height of binary tree – C | C++Java
  • Find maximum in binary tree – C | C++Java
  • Check whether two tree are identical- CC++Java
  • Spiral Order traversal of Tree- CC++Java
  • Level Order Traversal Line by Line – C | C++Java
  • Hand shaking lemma and some Impotant Tree Properties.
  • Check If binary tree if Foldable or not.- CC++Java
  • check whether tree is Symmetric – C| C++Java.
  • Check for Children-Sum in Binary Tree- C|C++Java
  • Sum of all nodes in Binary Tree- CC++ | Java
  • Lowest Common Ancestor in Binary Tree- CC++ | Java

Introduction to Trees

Binary Trees

Binary Search Trees

Traversals

  • Traversal in Trees
  • Tree Traversals: Breadth-First Search (BFS) : C | C++ | Java
  • Tree Traversals: Depth First Search (DFS) : C | C++ | Java
  • Construct a Binary Tree from Postorder and Inorder

B – Trees

AVL Trees

  • AVL Trees
    • AVL Trees: Introduction
    • AVL Tree Insertion :  C | C++ | Java
    • AVL Tree Deletion : C | C++ | Java
    • Insertion in a Binary Tree (Level Order) – C | C++ | Java
    • Searching in Binary Tree – C | C++ | Java
    • Searching in a Binary Search Tree – C | C++ | Java

Complete Programs for Trees

  • Depth First Traversals – C | C++ | Java
  • Level Order Traversal – C | C++Java
  • Construct Tree from given Inorder and Preorder traversals – C | C++Java
  • Construct Tree from given Postorder and Inorder traversals – C | C++Java
  • Construct Tree from given Postorder and Preorder traversal – C | C++Java
  • Find size of the Binary tree – C | C++Java
  • Find the height of binary tree – C | C++Java
  • Find maximum in binary tree – C | C++Java
  • Check whether two tree are identical- CC++Java
  • Spiral Order traversal of Tree- CC++Java
  • Level Order Traversal LIne by Line – C | C++Java
  • Hand shaking lemma and some Impotant Tree Properties.
  • Check If binary tree if Foldable or not.- CC++Java
  • check whether tree is Symmetric  C| C++Java.
  • Check for Children-Sum in Binary Tree- C|C++Java
  • Sum of all nodes in Binary Tree- CC++ | Java
  • Lowest Common Ancestor in Binary Tree. CC++ | Java

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