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.

Practice

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

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 subtree first, then the root node, and finally the right subtree.

2. Step 2: Match the traversal order to options

   Left subtree, Root, Right subtree correctly states the order as Left subtree, Root, Right subtree.

3. Final Answer:

   Left subtree, Root, Right subtree -> Option A

4. Quick Check:

   Inorder = Left, Root, Right [OK]

Hint: Inorder always visits left child before root [OK]

Common Mistakes:

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

2. Which of the following TypeScript function signatures correctly represents an inorder traversal function for a binary tree node?

easy

A. function inorder(node: TreeNode): number[]

B. function inorder(node: TreeNode | null): void

C. function inorder(): void

D. function inorder(node: TreeNode | null): number

Solution

1. Step 1: Analyze function parameters and return type

   An inorder traversal function typically takes a node or null as input and performs traversal, often printing or processing nodes without returning a value.

2. Step 2: Check options for correct signature

   function inorder(node: TreeNode | null): void accepts a node or null and returns void, which fits traversal that prints or processes nodes.

3. Final Answer:

   function inorder(node: TreeNode | null): void -> Option B

4. Quick Check:

   Traversal function takes node or null, returns void [OK]

Hint: Traversal functions usually take node or null, return void [OK]

Common Mistakes:

• Omitting null in parameter type
• Returning incorrect types like number or array
• Missing parameter in function signature

3. Given the following binary tree:

    2
   / \
  1   3

What is the output of inorder traversal printing node values?

medium

A. [2, 1, 3]

B. [3, 2, 1]

C. [1, 3, 2]

D. [1, 2, 3]

Solution

1. Step 1: Visualize the tree and inorder traversal

   Inorder visits left subtree, root, then right subtree. For root 2, left child is 1, right child is 3.

2. Step 2: List nodes in inorder

   Visit left: 1, then root: 2, then right: 3, so output is [1, 2, 3].

3. Final Answer:

   [1, 2, 3] -> Option D

4. Quick Check:

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

Hint: Inorder prints nodes sorted for BST [OK]

Common Mistakes:

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

4. Consider this TypeScript inorder traversal function:

function inorder(node: TreeNode | null): void {
  if (node === null) return;
  inorder(node.right);
  console.log(node.val);
  inorder(node.left);
}

What is the main problem with this code?

medium

A. It prints node values twice

B. It does not handle null nodes properly

C. It visits right subtree before left, so traversal order is incorrect

D. It causes infinite recursion

Solution

1. Step 1: Analyze traversal order in code

   The function calls inorder on right subtree first, then prints root, then calls inorder on left subtree.

2. Step 2: Compare with correct inorder order

   Correct inorder is left subtree, root, right subtree. This code reverses left and right, so order is wrong.

3. Final Answer:

   It visits right subtree before left, so traversal order is incorrect -> Option C

4. Quick Check:

   Inorder must visit left before right [OK]

Hint: Inorder must call left subtree before right [OK]

Common Mistakes:

• Swapping left and right subtree calls
• Forgetting base case for null
• Printing before recursive calls

5. You have a binary tree where each node contains a number. You want to collect all node values in an array using inorder traversal. Which TypeScript code snippet correctly implements this?

hard

A. function inorder(node: TreeNode | null, arr: number[]): void {
if (!node) return;
inorder(node.left, arr);
arr.push(node.val);
inorder(node.right, arr);
}

B. function inorder(node: TreeNode | null, arr: number[]): void {
if (!node) return;
arr.push(node.val);
inorder(node.left, arr);
inorder(node.right, arr);
}

C. function inorder(node: TreeNode | null, arr: number[]): void {
if (!node) return;
inorder(node.right, arr);
arr.push(node.val);
inorder(node.left, arr);
}

D. function inorder(node: TreeNode | null): number[] {
if (!node) return [];
return [node.val].concat(inorder(node.left)).concat(inorder(node.right));
}

Solution

1. Step 1: Understand inorder traversal with array accumulation

   We must visit left subtree, then root (push value), then right subtree, passing the same array to collect values.

2. Step 2: Check each option for correct order and array usage

   function inorder(node: TreeNode | null, arr: number[]): void { if (!node) return; inorder(node.left, arr); arr.push(node.val); inorder(node.right, arr); } correctly visits left, pushes root value, then visits right, using the same array.

3. Final Answer:

   function inorder(node: TreeNode | null, arr: number[]): void { if (!node) return; inorder(node.left, arr); arr.push(node.val); inorder(node.right, arr); } -> Option A

4. Quick Check:

   Left, root, right with shared array [OK]

Hint: Push node value after left subtree call [OK]

Common Mistakes:

• Pushing before left subtree traversal
• Swapping left and right subtree calls
• Returning new arrays instead of using passed array