.png)
DSA Series Chapter 14 – INORDER TRAVERSAL (BINARY TREE)
Objective:
This post explains Inorder Traversal of a Binary Tree in a standalone and detailed manner, suitable for:
Engineering examinations
Interview preparation
Strong recursion and traversal logic building
1. What is Inorder Traversal?
Definition (Exam‑Ready)
Inorder traversal is a depth‑first traversal technique in which the left subtree is visited first, then the root node, and finally the right subtree.
Traversal Order
Left → Root → Right
2. Binary Tree Diagram Used
1
/ \
2 3
/ \
4 5
The same tree is used for explanation, dry run, and program output.
3. Step‑by‑Step Inorder Traversal on Diagram
Traversal rule: Left → Root → Right
Start at root (1) → move to left subtree
At node 2 → move to its left subtree
At node 4 → left is NULL
Visit 4
Right of 4 is NULL → return to node 2
Visit 2
Traverse right subtree of 2
Visit 5
Return to root node 1
Visit 1
Traverse right subtree of root
Visit 3
Final Inorder Output
4 2 5 1 3
4. Algorithm (Recursive – Plain English)
If current node is NULL, return
Traverse left subtree recursively
Visit the current node
Traverse right subtree recursively
5. Recursive Algorithm (Pseudo Code)
INORDER(node)
{
if(node != NULL)
{
INORDER(node->left)
visit(node)
INORDER(node->right)
}
}
6. C Program – Inorder Traversal (Recursive)
#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node *left;
struct Node *right;
};
struct Node* createNode(int data)
{
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = data;
newNode->left = NULL;
newNode->right = NULL;
return newNode;
}
void inorder(struct Node* root)
{
if (root != NULL)
{
inorder(root->left);
printf("%d ", root->data);
inorder(root->right);
}
}
int main()
{
struct Node* root = createNode(1);
root->left = createNode(2);
root->right = createNode(3);
root->left->left = createNode(4);
root->left->right = createNode(5);
printf("Inorder Traversal: ");
inorder(root);
return 0;
}
7. Dry Run of Recursive Calls
inorder(1)
inorder(2)
inorder(4)
print 4
print 2
inorder(5)
print 5
print 1
inorder(3)
print 3
8. Time and Space Complexity
Time Complexity
O(n) — every node is visited once
Space Complexity
O(h) — recursion stack, where h = height of tree
Worst case (skewed tree): O(n)
9. Special Property (Very Important Concept)
Inorder Traversal of a BST
Inorder traversal of a Binary Search Tree produces sorted output.
⚠ Note: This property does NOT apply to a normal Binary Tree.
10. Important Applications of Inorder Traversal
Retrieving sorted data from BSTs
Expression tree evaluation (infix expression)
Structural analysis of trees
11. Common Exam & Interview Mistakes
Printing root before left subtree (becomes preorder)
Assuming inorder output is always sorted
Forgetting NULL base condition
12. Practice Questions
Write inorder traversal for a given binary tree diagram.
Predict inorder output for a left‑skewed tree.
Explain why inorder traversal of BST is sorted.
Convert recursive inorder traversal to iterative logic.
13. Learning Outcome (Post 3.2)
After this post, a student can:
Explain inorder traversal clearly
Dry‑run inorder traversal on any tree
Write inorder traversal program in C
Distinguish Binary Tree vs BST inorder behavior
ALSO CHECK
ALSO CHECK
Comments
Post a Comment