Tree Traversal Inorder Left Root Right in DSA C++

Mental Model

Visit the left side first, then the current node, then the right side. This order visits nodes in a sorted way for binary search trees.

Analogy: Imagine reading a book where you first read the left page, then the middle page, then the right page, so you don't miss anything and keep the order.

    2
   / \
  1   3

Traversal order: 1 -> 2 -> 3

Dry Run Walkthrough

Input: Binary tree: root=2, left child=1, right child=3; perform inorder traversal

Goal: Print nodes in left-root-right order to get sorted output

Step 1: Start at root (2), move to left child (1)

Current node: 1
Tree: 2 -> left: 1, right: 3

Why: In inorder, we visit left subtree first

Step 2: Node 1 has no left child, print 1

Output: 1
Current node: 1

Why: Left subtree done, now visit root

Step 3: Move back to parent (2), print 2

Output: 1 2
Current node: 2

Why: After left subtree, visit root

Step 4: Move to right child (3), no left child, print 3

Output: 1 2 3
Current node: 3

Why: Visit right subtree after root

Result:

Output: 1 2 3

Annotated Code

DSA C++

#include <iostream>
using namespace std;

struct Node {
    int data;
    Node* left;
    Node* right;
    Node(int val) : data(val), left(nullptr), right(nullptr) {}
};

void inorderTraversal(Node* root) {
    if (root == nullptr) return; // base case: empty node
    inorderTraversal(root->left); // visit left subtree
    cout << root->data << " "; // visit root
    inorderTraversal(root->right); // visit right subtree
}

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

    inorderTraversal(root);
    cout << endl;
    return 0;
}

if (root == nullptr) return; // base case: empty node

stop recursion when node is empty

inorderTraversal(root->left); // visit left subtree

recursively visit left child first

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

print current node after left subtree

inorderTraversal(root->right); // visit right subtree

recursively visit right child last

Output

1 2 3 

Complexity Analysis

Time: O(n) because each node is visited exactly once

Space: O(h) where h is tree height due to recursion stack

vs Alternative: Compared to iterative traversal, recursive is simpler but uses call stack; iterative uses explicit stack but same time complexity

Edge Cases

Empty tree (root is nullptr)

No output, function returns immediately

DSA C++

if (root == nullptr) return; // base case: empty node

Single node tree

Prints the single node value

DSA C++

if (root == nullptr) return; // base case: empty node

Left skewed tree (all nodes only have left child)

Prints nodes from bottom left up to root in order

DSA C++

inorderTraversal(root->left); // visit left subtree

When to Use This Pattern

When a problem asks to visit all nodes in sorted order in a binary search tree, use inorder traversal because it visits left, root, then right nodes.

Common Mistakes

Mistake: Visiting root before left subtree (preorder) instead of after
Fix: Move the print statement after the recursive call to left child

Mistake: Skipping the right subtree traversal
Fix: Add recursive call to right child after printing root

Summary

Visits nodes in left-root-right order to get sorted output for binary trees.

Use when you want to process nodes in ascending order or sorted sequence.

Remember: always visit left subtree first, then root, then right subtree.