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

↓

End

Inorder traversal visits nodes by going left subtree first, then the root node, then the right subtree.

Execution Sample

DSA C#

void Inorder(Node node) {
  if (node == null) return;
  Inorder(node.left);
  Console.Write(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	Left/Right	Tree State
1	Start at root	10	root	10 / \ 5 15
2	Traverse left subtree	5	left	10 / \ 5 15
3	Traverse left subtree	null	left of 5	10 / \ 5 15
4	Visit node	5	left leaf	10 / \ 5 15
5	Traverse right subtree	null	right of 5	10 / \ 5 15
6	Visit root node	10	root	10 / \ 5 15
7	Traverse right subtree	15	right	10 / \ 5 15
8	Traverse left subtree	null	left of 15	10 / \ 5 15
9	Visit node	15	right leaf	10 / \ 5 15
10	Traverse right subtree	null	right of 15	10 / \ 5 15
11	End	null	done	Traversal complete

💡 All nodes visited in inorder: left subtree, root, right subtree

Variable Tracker

Variable	Start	After Step 2	After Step 4	After Step 6	After Step 9	Final
current node	10	5	5	10	15	null
call stack	Inorder(10)	Inorder(10) -> Inorder(5)	Inorder(10)	Inorder(10) -> Inorder(15)	Inorder(10)	empty
output sequence			5	5 10	5 10 15	5 10 15

Key Moments - 3 Insights

Why do we visit the node after traversing the left subtree?

In inorder traversal, the rule is to visit left subtree first, then the node itself. This is shown in execution_table rows 2-4 where left subtree is fully traversed before visiting node 5.

What happens when the left or right child is null?

When a child is null, the traversal returns immediately without visiting any node. This is shown in rows 3, 5, 8, and 10 where traversal hits null and returns.

How does the call stack change during traversal?

The call stack grows when going deeper into left subtree and shrinks after visiting nodes and traversing right subtree. See variable_tracker showing call stack growing at step 2 and shrinking after step 9.

Visual Quiz - 3 Questions

Look at the execution_table, what node is visited at step 4?

A Node 15

B Node 10

C Node 5

D null

💡 Hint

Check the 'Node Visited' column at step 4 in execution_table

At which step does the traversal visit the root node 10?

A Step 6

B Step 2

C Step 4

D Step 9

💡 Hint

Look for 'Visit root node' operation in execution_table

If the left child of node 5 was not null, how would the execution_table change?

A Fewer steps overall

B More steps before visiting node 5

C Node 5 would be visited before its left child

D Traversal would skip node 10

💡 Hint

In inorder, left subtree is fully traversed before visiting node; see steps 2-4

Concept Snapshot

Inorder Tree Traversal (Left, Root, Right):
- Visit left subtree recursively
- Visit current node
- Visit right subtree recursively
Use recursion or stack
Output is sorted for BST
Null child means return immediately

Full Transcript

Inorder traversal visits nodes in the order: left subtree, root node, then right subtree. Starting at the root, the traversal goes as far left as possible, visiting nodes only after their left children are processed. When a null child is reached, the function returns immediately. The call stack grows as recursion goes deeper and shrinks as nodes are visited and right subtrees are processed. The output sequence for the example tree with nodes 5, 10, 15 is 5 10 15.

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

2. Step 2: Apply the order to the tree nodes

   This order ensures nodes are visited in ascending order for binary search trees.

3. Final Answer:

   Left subtree, Root, Right subtree -> Option A

4. Quick Check:

   Inorder = Left, Root, Right [OK]

Hint: Remember: Inorder = Left, Root, 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 C# method signatures correctly represents an inorder traversal method for a binary tree node class named Node?

easy

A. void InorderTraversal(Node root)

B. int InorderTraversal(Node root)

C. Node InorderTraversal()

D. bool InorderTraversal(Node root)

Solution

1. Step 1: Identify the purpose of the method

   An inorder traversal method typically visits nodes and prints or processes them without returning a value, so it should be void.

2. Step 2: Check method signature options

   void InorderTraversal(Node root) uses void return type and accepts a Node parameter, which is correct for traversal.

3. Final Answer:

   void InorderTraversal(Node root) -> Option A

4. Quick Check:

   Traversal methods usually return void [OK]

Hint: Traversal methods usually return void [OK]

Common Mistakes:

• Using return types like int or bool unnecessarily
• Missing the root parameter
• Returning Node instead of void

3. Given the following binary tree:

    2
   / \
  1   3

What is the output of the inorder traversal method that prints node values?

medium

A. 1 3 2

B. 2 1 3

C. 3 2 1

D. 1 2 3

Solution

1. Step 1: Apply inorder traversal on the tree

   Visit left subtree (1), then root (2), then right subtree (3).

2. Step 2: Write the visited nodes in order

   The nodes are visited in order: 1, 2, 3.

3. Final Answer:

   1 2 3 -> Option D

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
• Swapping left and right subtree order
• Confusing with preorder or postorder output

4. Consider this C# inorder traversal method:

void InorderTraversal(Node root) {
    if (root == null) return;
    InorderTraversal(root.Right);
    Console.Write(root.Value + " ");
    InorderTraversal(root.Left);
}

What is the error in this code?

medium

A. It causes infinite recursion

B. It misses the base case for null root

C. It visits right subtree before left subtree, reversing inorder order

D. It does not print the root value

Solution

1. Step 1: Analyze the traversal order in the code

   The code visits root.Right first, then root, then root.Left, which is reverse of inorder.

2. Step 2: Identify the correct inorder order

   Inorder should visit left subtree first, then root, then right subtree.

3. Final Answer:

   It visits right subtree before left subtree, reversing inorder order -> Option C

4. Quick Check:

   Inorder = Left, Root, Right [OK]

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

Common Mistakes:

• Swapping left and right subtree calls
• Forgetting to check for null root
• Not printing root value

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

hard

A. void Inorder(Node root, List<int> result) {
if (root == null) return;
result.Add(root.Value);
Inorder(root.Left, result);
Inorder(root.Right, result);
}

B. void Inorder(Node root, List<int> result) {
if (root == null) return;
Inorder(root.Left, result);
result.Add(root.Value);
Inorder(root.Right, result);
}

C. void Inorder(Node root, List<int> result) {
if (root == null) return;
Inorder(root.Right, result);
result.Add(root.Value);
Inorder(root.Left, result);
}

D. void Inorder(Node root, List<int> result) {
if (root == null) return;
Inorder(root.Left, result);
Inorder(root.Right, result);
result.Add(root.Value);
}

Solution

1. Step 1: Recall inorder traversal order

   Inorder visits left subtree, then root, then right subtree.

2. Step 2: Check which code matches this order

   void Inorder(Node root, List<int> result) { if (root == null) return; Inorder(root.Left, result); result.Add(root.Value); Inorder(root.Right, result); } visits left subtree, adds root value, then visits right subtree, correctly collecting values in order.

3. Final Answer:

   void Inorder(Node root, List<int> result) { if (root == null) return; Inorder(root.Left, result); result.Add(root.Value); Inorder(root.Right, result); } -> Option B

4. Quick Check:

   Left, Root, Right order with result.Add(root.Value) in middle [OK]

Hint: Add root value between left and right recursive calls [OK]

Common Mistakes:

• Adding root value before left subtree
• Adding root value after right subtree
• Swapping left and right subtree calls