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.