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

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

Execution Sample

DSA Javascript

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

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

Execution Table

Step	Operation	Node Visited	Pointer Changes	Tree State (Visual)
1	Start at root	10	current = 10	10 / \ 5 15
2	Traverse left subtree	5	current = 5	10 / \ 5 15
3	Traverse left subtree	null	current = null	10 / \ 5 15
4	Visit node	5	print 5	10 / \ 5 15
5	Traverse right subtree	null	current = null	10 / \ 5 15
6	Return to root	10	current = 10	10 / \ 5 15
7	Visit node	10	print 10	10 / \ 5 15
8	Traverse right subtree	15	current = 15	10 / \ 5 15
9	Traverse left subtree	null	current = null	10 / \ 5 15
10	Visit node	15	print 15	10 / \ 5 15
11	Traverse right subtree	null	current = null	10 / \ 5 15
12	Traversal complete	null	current = null	10 / \ 5 15

💡 Traversal ends when all nodes have been visited and current pointer is null.

Variable Tracker

Variable	Start	After Step 2	After Step 6	After Step 8	Final
current	10 (root)	5 (left child)	10 (root)	15 (right child)	null (end)
printed_values	[]	[]	[5]	[5, 10]	[5, 10, 15]

Key Moments - 3 Insights

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

In the execution_table at steps 2 and 4, we see the traversal goes left first to node 5 before printing it, ensuring left nodes are processed before the root.

What happens when the current node is null?

At steps 3, 5, 9, and 11, current becomes null, which means there is no child node to visit, so the function returns and backtracks to the previous node.

Why do we print the node value after traversing the left subtree?

Step 4 shows printing after left traversal, ensuring the left subtree is fully processed before visiting the root, following the inorder rule.

Visual Quiz - 3 Questions

Look at the execution_table, what is the printed value at step 7?

A 10

B 5

C 15

D null

💡 Hint

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

At which step does the traversal visit the right child of the root node?

A Step 2

B Step 8

C Step 6

D Step 10

💡 Hint

Look for 'Traverse right subtree' operation and 'Node Visited' being 15 in the execution_table.

If the left child of the root was null, how would the printed values change?

A [5, 10, 15]

B [15, 10, 5]

C [10, 15]

D [10]

💡 Hint

Refer to variable_tracker and consider what happens when left subtree traversal is skipped.

Concept Snapshot

Inorder traversal visits nodes in Left → Root → Right order.
Use recursion: traverse left subtree, visit node, traverse right subtree.
Print node value after left subtree is done.
Useful for binary search trees to get sorted order.
Stops when all nodes are visited (null reached).

Full Transcript

Inorder traversal means visiting the left child first, then the root node, and finally the right child. The code uses recursion to go as far left as possible, then prints the node's value, and then goes right. The execution table shows each step: starting at root 10, going left to 5, printing 5, returning to 10, printing 10, then going right to 15 and printing 15. When a node is null, the function returns and backtracks. This traversal order is useful because it prints nodes in sorted order for binary search trees.

Practice

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

easy

A. Root, Right subtree, Left subtree

B. Left subtree, Root, Right subtree

C. Right subtree, Root, Left subtree

D. Root, Left subtree, Right 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 B

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 is the correct JavaScript function signature for inorder traversal of a binary tree node named node?

easy

A. function inorder(node) { inorder(node.right); console.log(node.value); inorder(node.left); }

B. function inorder(node) { console.log(node.value); inorder(node.left); inorder(node.right); }

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

D. function inorder(node) { inorder(node.left); inorder(node.right); console.log(node.value); }

Solution

1. Step 1: Recall inorder traversal steps in code

   Inorder traversal visits left subtree, then root, then right subtree. So the function must call inorder on left, print root, then call inorder on right.

2. Step 2: Check each option's order

   function inorder(node) { if(node) { inorder(node.left); console.log(node.value); inorder(node.right); } } matches the correct order: left, root (console.log), right. Others have wrong orders.

3. Final Answer:

   function inorder(node) { if(node) { inorder(node.left); console.log(node.value); inorder(node.right); } } -> Option C

4. Quick Check:

   Left, Root, Right in code = function inorder(node) { if(node) { inorder(node.left); console.log(node.value); inorder(node.right); } } [OK]

Hint: Inorder prints after left call, before right call [OK]

Common Mistakes:

• Printing before left subtree traversal
• Swapping left and right subtree calls
• Missing null check for node

3. Given the binary tree below, what is the output of inorder traversal?

    10
   /  \
  5    15
 /    /  \
3    12  20

medium

A. [3, 5, 10, 12, 15, 20]

B. [10, 5, 3, 15, 12, 20]

C. [3, 5, 12, 10, 15, 20]

D. [5, 3, 10, 15, 12, 20]

Solution

1. Step 1: Traverse left subtree of root 10

   Left subtree of 10 is rooted at 5. Its left child is 3. Inorder of left subtree: visit 3, then 5 (root of subtree).

2. Step 2: Visit root 10 and then right subtree

   After left subtree, visit root 10. Then traverse right subtree rooted at 15: left child 12, root 15, right child 20. So inorder right subtree is 12, 15, 20.

3. Final Answer:

   [3, 5, 10, 12, 15, 20] -> Option A

4. Quick Check:

   Inorder = Left, Root, Right = [3,5,10,12,15,20] [OK]

Hint: List nodes left-root-right recursively [OK]

Common Mistakes:

• Visiting root before left subtree
• Mixing order of right subtree nodes
• Skipping leaf nodes

4. The following JavaScript code is intended to perform inorder traversal but has a bug. What is the bug?

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

medium

A. It prints the root before left subtree, so not inorder

B. It does not check for null nodes

C. It misses traversing the right subtree

D. It calls inorder on left and right in wrong order

Solution

1. Step 1: Analyze the order of operations in code

   The code prints node.value first, then calls inorder on left and right. This is preorder traversal order.

2. Step 2: Identify correct inorder order

   Inorder traversal requires visiting left subtree first, then printing root, then right subtree. The code prints root before left subtree, which is incorrect.

3. Final Answer:

   It prints the root before left subtree, so not inorder -> Option A

4. Quick Check:

   Print after left call for inorder [OK]

Hint: Print after left subtree call for inorder [OK]

Common Mistakes:

• Printing root before left subtree
• Confusing preorder with inorder
• Not checking for null nodes (though code does here)

5. You have a binary search tree (BST) and want to get all values in ascending order using inorder traversal. Which of the following modifications to the inorder traversal function will correctly collect values into an array instead of printing them?

function inorder(node, arr) {
  if (!node) return;
  // Fill missing code here
}

hard

A. inorder(node.left, arr); inorder(node.right, arr); arr.push(node.value);

B. arr.push(node.value); inorder(node.left, arr); inorder(node.right, arr);

C. inorder(node.right, arr); arr.push(node.value); inorder(node.left, arr);

D. inorder(node.left, arr); arr.push(node.value); inorder(node.right, arr);

Solution

1. Step 1: Recall inorder traversal order for BST

   Inorder traversal visits left subtree, then root, then right subtree, which returns values in ascending order for BST.

2. Step 2: Choose code that collects values in correct order

   inorder(node.left, arr); arr.push(node.value); inorder(node.right, arr); calls inorder on left, then pushes current node value, then calls inorder on right, correctly collecting values in ascending order.

3. Final Answer:

   inorder(node.left, arr); arr.push(node.value); inorder(node.right, arr); -> Option D

4. Quick Check:

   Left, Root, Right with push = inorder(node.left, arr); arr.push(node.value); inorder(node.right, arr); [OK]

Hint: Push after left call, before right call for sorted array [OK]

Common Mistakes:

• Pushing before left subtree traversal
• Swapping left and right subtree calls
• Pushing after both subtree traversals