Tree Traversal Inorder Left Root Right in DSA Typescript - 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 traversal

The traversal visits left subtree first, then the root node, then the right subtree recursively.

Execution Sample

DSA Typescript

function inorder(node) {
  if (!node) return;
  inorder(node.left);
  console.log(node.value);
  inorder(node.right);
}

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

Execution Table

Step	Operation	Node Visited	Pointer Changes	Tree State (Visual)
1	Start traversal	A (root)	Current = A	A ├─ B └─ C
2	Traverse left subtree	B	Current = B	A ├─ B └─ C
3	Traverse left subtree	D	Current = D	A ├─ B │ ├─ D │ └─ E └─ C
4	Traverse left subtree	null	Current = null	A ├─ B │ ├─ D │ └─ E └─ C
5	Visit node	D	Print D	A ├─ B │ ├─ D │ └─ E └─ C
6	Traverse right subtree	null	Current = null	A ├─ B │ ├─ D │ └─ E └─ C
7	Return to parent	B	Current = B	A ├─ B │ ├─ D │ └─ E └─ C
8	Traverse right subtree	E	Current = E	A ├─ B │ ├─ D │ └─ E └─ C
9	Traverse left subtree	null	Current = null	A ├─ B │ ├─ D │ └─ E └─ C
10	Visit node	E	Print E	A ├─ B │ ├─ D │ └─ E └─ C
11	Traverse right subtree	null	Current = null	A ├─ B │ ├─ D │ └─ E └─ C
12	Return to parent	B	Current = B	A ├─ B │ ├─ D │ └─ E └─ C
13	Return to parent	A	Current = A	A ├─ B │ ├─ D │ └─ E └─ C
14	Visit node	A	Print A	A ├─ B │ ├─ D │ └─ E └─ C
15	Traverse right subtree	C	Current = C	A ├─ B │ ├─ D │ └─ E └─ C
16	Traverse left subtree	null	Current = null	A ├─ B │ ├─ D │ └─ E └─ C
17	Visit node	C	Print C	A ├─ B │ ├─ D │ └─ E └─ C
18	Traverse right subtree	null	Current = null	A ├─ B │ ├─ D │ └─ E └─ C
19	End traversal	null	Traversal complete	A ├─ B │ ├─ D │ └─ E └─ C

💡 Traversal ends when all nodes have been visited in left-root-right order.

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 7	After Step 13	After Step 15	Final
Current Node	A	B	D	B	A	C	null
Printed Nodes	[]	[]	[]	[D]	[D, B, E]	[D, B, E, A]	[D, B, E, A, C]

Key Moments - 3 Insights

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

Because inorder traversal means visiting left child first, then root, then right child. See execution_table steps 2-5 where left subtree nodes are visited before printing root B at step 8.

What happens when the current node is null?

The traversal returns immediately without printing. This is shown in steps 4, 6, 9, 11, 16, and 18 where current node is null and traversal moves back up.

How do we know when traversal is complete?

When all nodes have been visited and returned from, current node becomes null at the top level (step 19). The exit_note confirms traversal ends after all nodes are printed.

Visual Quiz - 3 Questions

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

A D

B E

C B

D A

💡 Hint

Check the 'Operation' and 'Node Visited' columns at step 10 in execution_table.

At which step does the traversal return to the root node A after visiting left subtree?

A Step 7

B Step 15

C Step 13

D Step 19

💡 Hint

Look for 'Return to parent' operation with node A in execution_table.

If the left subtree of B was empty, how would the printed nodes order change?

A D would be missing, printed order starts with B

B E would be printed before B

C Traversal would print A before B

D No change in printed order

💡 Hint

Refer to variable_tracker and execution_table steps 2-5 where left subtree nodes are printed before B.

Concept Snapshot

Inorder Tree Traversal:
- Visit left subtree recursively
- Visit root node
- Visit right subtree recursively
Print nodes in left-root-right order
Used for sorted output in BST
Base case: node is null, return immediately

Full Transcript

Inorder traversal visits nodes in the order left child, root, then right child. Starting at the root, it recursively visits the left subtree until it reaches a null node, then prints the current node's value, then recursively visits the right subtree. This process continues until all nodes are visited. The execution table shows each step, including visiting nodes, printing values, and returning when reaching null. The variable tracker shows how the current node pointer moves and which nodes are printed in order. Key moments clarify why left subtree is visited first, what happens at null nodes, and when traversal ends. The visual quiz tests understanding of printed nodes at specific steps and effects of subtree changes.