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

↓

Return to parent or end

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

Execution Sample

DSA C++

struct Node {
  int val;
  Node* left;
  Node* right;
};

void inorder(Node* root) {
  if (!root) return;
  inorder(root->left);
  std::cout << root->val << " ";
  inorder(root->right);
}

This code recursively visits left child, prints root value, then visits 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 of 1	1 / \ 2 3
3	Traverse left subtree	4	left of 2	1 / \ 2 3 / 4
4	Visit node	4	left leaf	4 visited
5	Return to parent	2	back to 2	4 visited
6	Visit node	2	left child	4 -> 2 visited
7	Traverse right subtree	5	right of 2	4 -> 2 visited
8	Visit node	5	right leaf	4 -> 2 -> 5 visited
9	Return to parent	1	back to 1	4 -> 2 -> 5 visited
10	Visit node	1	root	4 -> 2 -> 5 -> 1 visited
11	Traverse right subtree	3	right of 1	4 -> 2 -> 5 -> 1 visited
12	Traverse left subtree	6	left of 3	4 -> 2 -> 5 -> 1 visited
13	Visit node	6	left leaf	4 -> 2 -> 5 -> 1 -> 6 visited
14	Return to parent	3	back to 3	4 -> 2 -> 5 -> 1 -> 6 visited
15	Visit node	3	right child	4 -> 2 -> 5 -> 1 -> 6 -> 3 visited
16	Traverse right subtree	7	right of 3	4 -> 2 -> 5 -> 1 -> 6 -> 3 visited
17	Visit node	7	right leaf	4 -> 2 -> 5 -> 1 -> 6 -> 3 -> 7 visited
18	Traversal complete	null	end	4 -> 2 -> 5 -> 1 -> 6 -> 3 -> 7 visited

💡 All nodes visited in left-root-right order, traversal ends.

Variable Tracker

Variable	Start	After Step 4	After Step 6	After Step 8	After Step 10	After Step 13	After Step 15	After Step 17	Final
Current Node	1	4	2	5	1	6	3	7	null
Visited Nodes	[]	[4]	[4,2]	[4,2,5]	[4,2,5,1]	[4,2,5,1,6]	[4,2,5,1,6,3]	[4,2,5,1,6,3,7]	[4,2,5,1,6,3,7]

Key Moments - 3 Insights

Why do we visit the left subtree before the root node?

In the execution_table at steps 2-4, the traversal goes deep into the left subtree first, ensuring all left children are visited before the root, following the left-root-right order.

What happens when a node has no left child?

At step 4 and step 8, when the node has no left child, the traversal visits the node itself immediately, as shown by visiting node 4 and node 5.

How does the traversal know when to stop?

At step 18, the traversal ends when all nodes have been visited and the recursive calls return null, indicating no more nodes to visit.

Visual Quiz - 3 Questions

Look at the execution_table, what is the current node at step 10?

A Node 3

B Node 2

C Node 1

D Node 5

💡 Hint

Check the 'Current Node' variable in variable_tracker after step 10.

At which step does the traversal visit node 6?

A Step 12

B Step 13

C Step 15

D Step 17

💡 Hint

Look at the 'Operation' and 'Node Visited' columns in execution_table for node 6.

If the left subtree of node 2 was empty, which step would be skipped?

A Step 3

B Step 4

C Step 6

D Step 7

💡 Hint

Step 3 shows traversal into left subtree of node 2; if empty, this step would not occur.

Concept Snapshot

Inorder Tree Traversal:
- Visit left subtree recursively
- Visit root node
- Visit right subtree recursively

Use recursion or stack
Order: Left → Root → Right
Common for sorted output of BST

Full Transcript

Inorder traversal visits nodes in the order left subtree, root, then right subtree. Starting at the root, it recursively goes to the left child until it reaches a leaf. Then it visits that node, returns to the parent, visits it, and then traverses the right child. This process repeats until all nodes are visited. The execution table shows each step visiting nodes 4, 2, 5, 1, 6, 3, and 7 in that order. Variables track the current node and the list of visited nodes. Key moments clarify why left subtree is visited first, what happens when no left child exists, and when traversal ends. The visual quiz tests understanding of node visits at specific steps and effects of missing subtrees.

Practice

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

easy

A. Right subtree, Root, Left subtree

B. Root, Left subtree, Right subtree

C. Left subtree, Root, Right subtree

D. Root, Right subtree, Left subtree

Solution

1. Step 1: Understand inorder traversal definition

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

2. Step 2: Apply to binary tree traversal

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

3. Final Answer:

   Left subtree, Root, Right subtree -> Option C

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 is the correct C++ function signature for inorder traversal of a binary tree node pointer Node* root?

easy

A. int inorderTraversal(Node* root)

B. int inorderTraversal(Node root)

C. void inorderTraversal(Node root)

D. void inorderTraversal(Node* root)

Solution

1. Step 1: Identify correct parameter type

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

2. Step 2: Identify correct return type

   Traversal functions typically return void because they print or process nodes without returning a value.

3. Final Answer:

   void inorderTraversal(Node* root) -> Option D

4. Quick Check:

   Pointer parameter and void return [OK]

Hint: Traversal functions use Node* and void return [OK]

Common Mistakes:

• Passing node by value instead of pointer
• Using int return type instead of void
• Missing pointer symbol * in parameter

3. Given the binary tree:

    2
   / \
  1   3

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

medium

A. 1 2 3

B. 2 1 3

C. 3 2 1

D. 1 3 2

Solution

1. Step 1: Traverse left subtree

   Start at root (2), go left to node (1), print 1 since it has no left child.

2. Step 2: Visit root and right subtree

   Return to root (2), print 2, then go right to node (3), print 3.

3. Final Answer:

   1 2 3 -> Option A

4. Quick Check:

   Inorder traversal output = 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++ inorder traversal code snippet:

void inorder(Node* root) {
  if (root == nullptr) return;
  inorder(root->left);
  std::cout << root->val << " ";
  inorder(root->right);
}

What is the error if the output is empty for a non-empty tree?

medium

A. The base case condition is incorrect

B. The function is not called with the root node

C. The print statement is missing

D. The traversal order is wrong

Solution

1. Step 1: Check base case correctness

   The base case correctly returns when root is nullptr, so no error here.

2. Step 2: Verify function call

   If output is empty, likely the function was never called with the actual root node of the tree.

3. Final Answer:

   The function is not called with the root node -> Option B

4. Quick Check:

   Missing initial call causes no output [OK]

Hint: Always call traversal with actual root node [OK]

Common Mistakes:

• Not calling traversal function at all
• Calling with nullptr instead of root
• Assuming print statement missing when it exists

5. You have a binary tree with nodes:

      4
     / \
    2   6
   / \ / \
  1  3 5  7

Using inorder traversal, which sequence of node values will you get?

hard

A. [1, 2, 3, 4, 5, 6, 7]

B. [4, 2, 1, 3, 6, 5, 7]

C. [7, 6, 5, 4, 3, 2, 1]

D. [1, 3, 2, 5, 7, 6, 4]

Solution

1. Step 1: Traverse left subtree of root (4)

   Visit left subtree rooted at 2: inorder visits 1, then 2, then 3.

2. Step 2: Visit root and right subtree

   After left subtree, visit root 4, then right subtree rooted at 6: visit 5, then 6, then 7.

3. Final Answer:

   [1, 2, 3, 4, 5, 6, 7] -> Option A

4. Quick Check:

   Inorder traversal of BST gives sorted sequence [OK]

Hint: Inorder traversal of BST returns sorted node values [OK]

Common Mistakes:

• Mixing preorder or postorder sequences
• Visiting root before left subtree
• Visiting right subtree before root