DSA In-order Traversal

DSA In-order Traversal – Complete Beginner Guide

(Concept • Steps • Example • Code • Complexity)

In-order Traversal is one of the Depth-First Search (DFS) traversal techniques for Binary Trees.
It is extremely important because in a Binary Search Tree (BST) it gives elements in sorted order.

1️⃣ What is In-order Traversal?

In In-order Traversal, nodes are visited in this order:

Left → Root → Right

The root node is visited between the left and right subtrees.

2️⃣ Easy Way to Remember

So:

3️⃣ In-order Traversal – Step by Step

Example Binary Tree

Traversal Steps

Go to leftmost node → 4
Visit parent → 2
Visit right child → 5
Visit root → 1
Visit right subtree → 3

Output

4️⃣ In-order Traversal Algorithm

Traverse the left subtree
Visit the root node
Traverse the right subtree

5️⃣ Pseudocode

6️⃣ In-order Traversal – Recursive Code (C++)

7️⃣ Complete Example Program (C++)

#include <iostream>
using namespace std;struct Node {
int data;
Node* left;
Node* right;
};Node* newNode(int value) {
Node* node = new Node();
node->data = value;
node->left = node->right = NULL;
return node;
}

void inorder(Node* root) {
if (root == NULL) return;
inorder(root->left);
cout << root->data << " ";
inorder(root->right);
}

int main() {
Node* root = newNode(1);
root->left = newNode(2);
root->right = newNode(3);
root->left->left = newNode(4);
root->left->right = newNode(5);

inorder(root);
return 0;
}

#include <iostream>

using namespace std;struct Node {

int data;

Node* left;

Node* right;

};Node* newNode(int value) {

Node* node = new Node();

node->data = value;

node->left = node->right = NULL;

return node;

}

void inorder(Node* root) {

if (root == NULL) return;

inorder(root->left);

cout << root->data << " ";

inorder(root->right);

}

int main() {

Node* root = newNode(1);

root->left = newNode(2);

root->right = newNode(3);

root->left->left = newNode(4);

root->left->right = newNode(5);

inorder(root);

return 0;

}

Output

8️⃣ Iterative In-order Traversal (Using Stack)

#include <stack>

void inorderIterative(Node* root) {
stack<Node*> st;
Node* curr = root;

while (curr != NULL || !st.empty()) {
while (curr != NULL) {
st.push(curr);
curr = curr->left;
}

curr = st.top();
st.pop();
cout << curr->data << " ";
curr = curr->right;
}
}

#include <stack>

void inorderIterative(Node* root) {

stack<Node*> st;

Node* curr = root;

while (curr != NULL || !st.empty()) {

while (curr != NULL) {

st.push(curr);

curr = curr->left;

}

curr = st.top();

st.pop();

cout << curr->data << " ";

curr = curr->right;

}

9️⃣ Time & Space Complexity

Time Complexity

Space Complexity

Recursive: O(h)
Iterative: O(h)
(h = height of tree)

🔟 Special Importance in BST

For a Binary Search Tree:

Example BST

In-order Output:

1️⃣1️⃣ In-order vs Pre-order vs Post-order

Traversal	Order
In-order	Left → Root → Right
Pre-order	Root → Left → Right
Post-order	Left → Right → Root

Interview Questions (In-order)

Q1. Why is in-order traversal important?
👉 Gives sorted data in BST

Q2. Can in-order traversal be done without recursion?
👉 Yes, using a stack

Q3. Time complexity?
👉 O(n)

Final Summary

✔ In-order traversal visits root in the middle
✔ Order: Left → Root → Right
✔ Crucial for BST sorting
✔ Implemented recursively or iteratively
✔ Time complexity: O(n)

DSA In-order Traversal