Tree Traversal Inorder Left Root Right in DSA C

Mental Model

Visit the left side first, then the middle, then the right side to see all parts in order.

Analogy: Like reading a book: first look at the left page, then the middle page, then the right page.

    2
   / \
  1   3

↑ Start at root (2)

Dry Run Walkthrough

Input: Tree: root=2, left=1, right=3

Goal: Print nodes in order: left child, root, right child

Step 1: Go left from root (2) to node 1

1 ↑ (at left child of 2) -> null
2 -> 3 -> null

Why: We visit left subtree first in inorder

Step 2: Print node 1

Output: 1

Why: Left node visited before root

Step 3: Return to root (2) and print it

Output: 1 2

Why: After left subtree, visit root

Step 4: Go right from root (2) to node 3

3 ↑ (at right child of 2)

Why: Visit right subtree last

Step 5: Print node 3

Output: 1 2 3

Why: Right node visited after root

Result:

Output: 1 2 3

Annotated Code

DSA C

#include <stdio.h>
#include <stdlib.h>

// Define tree node
typedef struct Node {
    int data;
    struct Node* left;
    struct Node* right;
} Node;

// Create new node
Node* newNode(int data) {
    Node* node = (Node*)malloc(sizeof(Node));
    node->data = data;
    node->left = NULL;
    node->right = NULL;
    return node;
}

// Inorder traversal: left, root, right
void inorder(Node* root) {
    if (root == NULL) return; // base case: no node
    inorder(root->left); // visit left subtree
    printf("%d ", root->data); // visit root
    inorder(root->right); // visit right subtree
}

int main() {
    // Build tree: 2 with left 1 and right 3
    Node* root = newNode(2);
    root->left = newNode(1);
    root->right = newNode(3);

    inorder(root); // print inorder traversal
    printf("\n");
    return 0;
}

if (root == NULL) return; // base case: no node

stop when no node to visit

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

go left first to visit left subtree

printf("%d ", root->data); // visit root

print current node after left subtree

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

go right last to visit right subtree

Output

1 2 3 

Complexity Analysis

Time: O(n) because we visit every node exactly once

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

vs Alternative: Compared to preorder or postorder, inorder also visits all nodes once, same time complexity

Edge Cases

Empty tree (root is NULL)

No output, function returns immediately

DSA C

if (root == NULL) return; // base case: no node

Single node tree

Prints the single node value

DSA C

if (root == NULL) return; // base case: no node

Left skewed tree (all nodes only have left child)

Prints nodes from bottom left up to root in order

DSA C

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

When to Use This Pattern

When you need to visit nodes in sorted order for a binary search tree, use inorder traversal because it visits left, root, then right.

Common Mistakes

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

Mistake: Forgetting to check if node is NULL before recursion
Fix: Add base case to return immediately if node is NULL

Summary

It visits nodes in the order: left child, root, then right child.

Use it when you want to see nodes in sorted order in a binary search tree.

The key is to first go all the way left, then visit root, then go right.

Practice

1. What is the order of nodes visited in an inorder tree traversal?

easy

A. Left subtree, Root, Right subtree

B. Root, Left subtree, Right subtree

C. Right subtree, Root, Left subtree

D. Root, Right subtree, Left subtree

Solution

1. Step 1: Understand inorder traversal definition

   Inorder traversal visits nodes in the order: left child, root node, then right child.

2. Step 2: Apply the order to the tree

   This means we first visit all nodes in the left subtree, then the root, then all nodes in the right subtree.

3. Final Answer:

   Left subtree, Root, Right subtree -> Option A

4. Quick Check:

   Inorder = Left, Root, Right [OK]

Hint: Remember: Inorder means Left, Root, then Right [OK]

Common Mistakes:

• Confusing inorder with preorder or postorder
• Visiting root before left subtree
• Visiting right subtree before root

2. Which of the following C function prototypes correctly represents an inorder traversal of a binary tree node struct Node?

easy

A. int inorder(struct Node* root);

B. int inorder(struct Node root);

C. void inorder(struct Node root);

D. void inorder(struct Node* root);

Solution

1. Step 1: Identify correct parameter type for tree traversal

   Traversal functions usually take a pointer to the root node to access the tree nodes.

2. Step 2: Check return type and parameter

   Traversal functions typically return void as they print or process nodes during traversal, so void return type with pointer parameter is correct.

3. Final Answer:

   void inorder(struct Node* root); -> Option D

4. Quick Check:

   Traversal uses pointer and void return [OK]

Hint: Traversal functions use pointer to root and void return [OK]

Common Mistakes:

• Passing struct by value instead of pointer
• Using int return type instead of void
• Missing pointer in parameter

3. Given the binary tree below:

    2
   / \
  1   3

What is the output of the inorder traversal function that prints node values?

medium

A. 2 1 3

B. 1 3 2

C. 1 2 3

D. 3 2 1

Solution

1. Step 1: Identify inorder traversal order

   Inorder visits left subtree, then root, then right subtree.

2. Step 2: Apply inorder to given tree

   Left child is 1, root is 2, right child is 3, so output is "1 2 3".

3. Final Answer:

   1 2 3 -> Option C

4. Quick Check:

   Inorder of 2-node tree = 1 2 3 [OK]

Hint: Inorder prints nodes in ascending order for BST [OK]

Common Mistakes:

• Printing root before left subtree
• Printing right subtree before root
• Confusing preorder or postorder output

4. Consider this C code snippet for inorder traversal:

void inorder(struct Node* root) {
    if (root == NULL) return;
    inorder(root->left);
    printf("%d ", root->data);
    inorder(root->right);
}

What is the error if the function prints nodes in preorder instead of inorder?

medium

A. The printf statement is before the left subtree call

B. The base case is missing the NULL check

C. The right subtree call is missing

D. The function is missing a return type

Solution

1. Step 1: Understand traversal order in code

   Inorder prints after left subtree call and before right subtree call.

2. Step 2: Identify cause of preorder output

   If printf is before left subtree call, root prints first, causing preorder output.

3. Final Answer:

   The printf statement is before the left subtree call -> Option A

4. Quick Check:

   Print before left subtree = preorder [OK]

Hint: Print root between left and right calls for inorder [OK]

Common Mistakes:

• Placing print before left subtree call
• Omitting NULL base case
• Forgetting to call right subtree

5. You have a binary search tree with nodes inserted in this order: 5, 3, 7, 2, 4, 6, 8.
What is the inorder traversal output of this tree?

hard

A. 5 3 7 2 4 6 8

B. 2 3 4 5 6 7 8

C. 8 7 6 5 4 3 2

D. 3 2 4 5 6 7 8

Solution

1. Step 1: Build the BST structure

   Insert 5 as root, 3 left of 5, 7 right of 5, 2 left of 3, 4 right of 3, 6 left of 7, 8 right of 7.

2. Step 2: Perform inorder traversal

   Inorder visits nodes in ascending order for BST: 2, 3, 4, 5, 6, 7, 8.

3. Final Answer:

   2 3 4 5 6 7 8 -> Option B

4. Quick Check:

   Inorder of BST = sorted nodes [OK]

Hint: Inorder traversal of BST gives sorted order [OK]

Common Mistakes:

• Listing nodes in insertion order
• Reversing the order
• Skipping nodes in traversal