Tree Traversal Inorder Left Root Right in DSA C - Execution Trace

Concept Flow - Tree Traversal Inorder Left Root Right

Start at root node

↓

Traverse left subtree

↓

Visit current node (root)

↓

Traverse right subtree

↓

End

Inorder traversal visits the left subtree first, then the root node, and finally the right subtree.

Execution Sample

DSA C

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

This code prints the nodes of a binary tree in inorder sequence: left child, root, right child.

Execution Table

Step	Operation	Node Visited	Left/Right	Tree State
1	Start at root	1	root	1 / \ 2 3
2	Traverse left subtree	2	left	1 / \ 2 3
3	Traverse left subtree	4	left of 2	1 / \ 2 3 / 4
4	Traverse left subtree	NULL	left of 4	No change
5	Visit node	4	left leaf	Output: 4
6	Traverse right subtree	NULL	right of 4	No change
7	Return to node	2	left subtree done	Output: 4
8	Visit node	2	root of left subtree	Output: 4 2
9	Traverse right subtree	5	right of 2	1 / \ 2 3 / \ 4 5
10	Traverse left subtree	NULL	left of 5	No change
11	Visit node	5	right leaf	Output: 4 2 5
12	Traverse right subtree	NULL	right of 5	No change
13	Return to root	1	left subtree done	Output: 4 2 5
14	Visit node	1	root	Output: 4 2 5 1
15	Traverse right subtree	3	right	1 / \ 2 3
16	Traverse left subtree	NULL	left of 3	No change
17	Visit node	3	right leaf	Output: 4 2 5 1 3
18	Traverse right subtree	NULL	right of 3	No change
19	End	NULL	all nodes visited	Output: 4 2 5 1 3

💡 Traversal ends after visiting all nodes in left-root-right order.

Variable Tracker

Variable	Start	After Step 2	After Step 7	After Step 13	After Step 19
current node	1 (root)	2 (left child)	2 (left subtree done)	1 (left subtree done)	NULL (done)
output sequence	empty	empty	4	4 2 5	4 2 5 1 3

Key Moments - 3 Insights

Why do we visit the node only after traversing its left subtree?

Because inorder traversal means left subtree first, then the node itself. See execution_table steps 4-5 and 7-8 where left subtree is fully visited before printing the node.

What happens when a node has no left or right child?

The traversal calls on NULL and returns immediately without action. This is shown in steps 4, 6, 10, 12, 16, and 18 where NULL nodes cause no change.

How does the traversal know when to stop?

When all nodes have been visited and recursive calls reach NULL, the traversal ends. This is shown at step 19 with output complete and current node NULL.

Visual Quiz - 3 Questions

Look at the execution_table, what is the output sequence after step 8?

A 4 2 5

B 4 2

C 4

D 2

💡 Hint

Check the 'Output' column at step 8 in the execution_table.

At which step does the traversal visit the root node (1)?

A Step 15

B Step 13

C Step 14

D Step 19

💡 Hint

Look for 'Visit node' operation with node 1 in the execution_table.

If node 2 had no right child, how would the output after step 13 change?

A 4 2

B 4 2 5 1

C 2 4 1

D 4 5 2 1

💡 Hint

Refer to variable_tracker and execution_table steps 9-12 where node 5 is visited.

Concept Snapshot

Inorder Tree Traversal:
- Visit left subtree first
- Then visit root node
- Finally visit right subtree
Syntax: inorder(node->left); visit(node); inorder(node->right);
Outputs nodes in ascending order for BST
Uses recursion to traverse all nodes

Full Transcript

Inorder traversal visits nodes in the order left subtree, root, then right subtree. Starting at the root, it recursively visits the left child until it reaches a leaf. Then it prints the node's value and moves to the right child. This process repeats until all nodes are visited. The example tree has nodes 1 as root, 2 and 3 as children, and 4 and 5 as children of 2. The output sequence after full traversal is 4 2 5 1 3. The traversal stops when all nodes have been visited and recursive calls reach NULL.

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