Binary Tree Inorder Traversal

What is Inorder Traversal?

Inorder traversal is a Depth-First Traversal method where we visit nodes in the following order:

1. Left subtree
2. Root node
3. Right subtree

This traversal results in nodes being visited in sorted order if the tree is a Binary Search Tree (BST).

Example

Consider the following binary tree:

Steps for Inorder Traversal:

1. Start from the root (1).
2. Visit the left subtree (2).
3. Visit the left subtree of (2) → (4) (no left child, so print 4).
4. Print 2 (after visiting left subtree).
5. Visit the right subtree of (2) → (5) (no left child, so print 5).
6. Print 1 (after visiting left subtree).
7. Visit the right subtree (3) (no left child, so print 3).

Inorder Traversal Output:

4 → 2 → 5 → 1 → 3

Applications of Inorder Traversal

• Sorting elements in a Binary Search Tree (BST).
• Expression tree evaluation (infix notation).
• Used in binary tree visualization tools.