Tree Traversal Preorder Root Left Right in DSA C# - Execution Trace

Concept Flow - Tree Traversal Preorder Root Left Right

Start at Root Node

↓

Visit Node: Process Data

↓

Traverse Left Subtree

↓

Traverse Right Subtree

↓

Done

Preorder traversal visits the root node first, then recursively visits the left subtree, followed by the right subtree.

Execution Sample

DSA C#

class Node {
  public int val;
  public Node left, right;
  public Node(int v) { val = v; }
}

void Preorder(Node root) {
  if (root == null) return;
  Console.Write(root.val + " ");
  Preorder(root.left);
  Preorder(root.right);
}

This code prints nodes in preorder: root first, then left subtree, then right subtree.

Execution Table

Step	Operation	Node Visited	Pointer Changes	Tree State (Visual)
1	Start at root	1	head=root(1)	1 / \ 2 3
2	Visit node	1	none	1 / \ 2 3
3	Traverse left subtree	2	move to left child	1 / \ 2 3
4	Visit node	2	none	1 / \ 2 3
5	Traverse left subtree	4	move to left child	1 / \ 2 3 / 4
6	Visit node	4	none	1 / \ 2 3 / 4
7	Traverse left subtree	null	move to left child	1 / \ 2 3 / 4
8	Reached null, backtrack	null	back to 4	1 / \ 2 3 / 4
9	Traverse right subtree	null	move to right child	1 / \ 2 3 / 4
10	Reached null, backtrack	null	back to 2	1 / \ 2 3 / 4
11	Traverse right subtree	5	move to right child	1 / \ 2 3 / 4 \ 5
12	Visit node	5	none	1 / \ 2 3 / 4 \ 5
13	Traverse left subtree	null	move to left child	1 / \ 2 3 / 4 \ 5
14	Reached null, backtrack	null	back to 5	1 / \ 2 3 / 4 \ 5
15	Traverse right subtree	null	move to right child	1 / \ 2 3 / 4 \ 5
16	Reached null, backtrack	null	back to 1	1 / \ 2 3 / 4 \ 5
17	Traverse right subtree	3	move to right child	1 / \ 2 3 / 4 \ 5
18	Visit node	3	none	1 / \ 2 3 / 4 \ 5
19	Traverse left subtree	null	move to left child	1 / \ 2 3 / 4 \ 5
20	Reached null, backtrack	null	back to 3	1 / \ 2 3 / 4 \ 5
21	Traverse right subtree	null	move to right child	1 / \ 2 3 / 4 \ 5
22	Reached null, backtrack	null	back to root, done	1 / \ 2 3 / 4 \ 5

💡 Traversal ends after visiting all nodes and reaching null children.

Variable Tracker

Variable	Start	After Step 3	After Step 5	After Step 11	After Step 17	Final
currentNode	root(1)	2	4	5	3	null
callStack	empty	[Preorder(1)]	[Preorder(1), Preorder(2)]	[Preorder(1), Preorder(2)]	[Preorder(1)]	empty
visitedNodes	[]	[1]	[1,2]	[1,2,4]	[1,2,4,5]	[1,2,4,5,3]

Key Moments - 3 Insights

Why do we visit the node before traversing its children?

Because preorder traversal means 'root first', so we print or process the node before going left or right, as shown in steps 2, 4, 6, 12, and 18 in the execution_table.

Why do we backtrack when we reach a null child?

Null means no child exists, so we return to the previous node to continue traversal. This is shown in steps 7-10 and 13-16 where traversal hits null and backtracks.

How does the call stack help in traversal?

The call stack remembers nodes to return to after finishing left subtree, enabling traversal of right subtree. variable_tracker shows callStack growing and shrinking as recursion proceeds.

Visual Quiz - 3 Questions

Look at the execution_table, which node is visited at step 12?

A Node 3

B Node 4

C Node 5

D Node 2

💡 Hint

Check the 'Node Visited' column at step 12 in execution_table.

At which step does the traversal move from the left subtree back to the root to start the right subtree?

A Step 16

B Step 10

C Step 22

D Step 5

💡 Hint

Look for 'back to 1' or root in Pointer Changes column in execution_table.

If the tree had no left child for node 2, how would the execution_table change at step 5?

A Step 5 would visit node 4 as usual

B Step 5 would be skipped and traversal would go directly to step 11

C Step 5 would visit node 3 instead

D Traversal would end early

💡 Hint

Check what happens when left child is null in steps 5-7 in execution_table.

Concept Snapshot

Preorder Traversal (Root, Left, Right):
- Visit current node first
- Recursively traverse left subtree
- Recursively traverse right subtree
- Uses recursion or stack
- Prints nodes in root-left-right order

Full Transcript

Preorder tree traversal visits the root node first, then the left subtree, then the right subtree. The code recursively visits nodes, printing the current node before moving left and right. The execution table shows each step visiting nodes 1, 2, 4, 5, and 3 in order, with backtracking when null children are reached. The variable tracker shows how the current node and call stack change during recursion. Key moments clarify why nodes are visited before children and how backtracking works. The visual quiz tests understanding of node visits and traversal flow. Preorder traversal is useful for copying trees or prefix expression evaluation.

Practice

1. What is the order of nodes visited in a preorder tree traversal?

easy

A. Left, Root, Right

B. Right, Left, Root

C. Left, Right, Root

D. Root, Left, Right

Solution

1. Step 1: Understand preorder traversal definition

   Preorder traversal visits the root node first, then recursively visits the left subtree, followed by the right subtree.

2. Step 2: Confirm the visiting order

   The visiting order is Root, then Left subtree, then Right subtree.

3. Final Answer:

   Root, Left, Right -> Option D

4. Quick Check:

   Preorder = Root, Left, Right [OK]

Hint: Remember: Preorder starts with the root node first [OK]

Common Mistakes:

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

2. Which of the following C# method signatures correctly represents a preorder traversal method for a binary tree node class named Node?

easy

A. void PreorderTraversal(Node root)

B. int PreorderTraversal(Node root)

C. Node PreorderTraversal()

D. void PreorderTraversal()

Solution

1. Step 1: Identify typical preorder traversal method signature

   Preorder traversal usually processes nodes and does not return a value, so it returns void and takes the root node as parameter.

2. Step 2: Match method signature options

   void PreorderTraversal(Node root) matches void return type and takes Node root parameter, which is correct.

3. Final Answer:

   void PreorderTraversal(Node root) -> Option A

4. Quick Check:

   Traversal method usually void with root parameter [OK]

Hint: Traversal methods usually return void and take root node [OK]

Common Mistakes:

• Using return type int instead of void
• Not passing root node as parameter
• Using method without parameters

3. Given the following binary tree:

    1
   / \
  2   3
 / \
4   5

What is the output of a preorder traversal printing node values?

medium

A. [1, 3, 2, 4, 5]

B. [4, 2, 5, 1, 3]

C. [1, 2, 4, 5, 3]

D. [2, 4, 5, 1, 3]

Solution

1. Step 1: Start preorder traversal at root node 1

   Visit root 1 first.

2. Step 2: Traverse left subtree of 1

   Visit node 2, then its left child 4, then right child 5.

3. Step 3: Traverse right subtree of 1

   Visit node 3.

4. Final Answer:

   [1, 2, 4, 5, 3] -> Option C

5. Quick Check:

   Preorder visits root, left subtree, right subtree [OK]

Hint: Visit root first, then left subtree, then right subtree [OK]

Common Mistakes:

• Mixing preorder with inorder or postorder output
• Visiting left subtree after right subtree
• Skipping leaf nodes

4. Consider this C# preorder traversal method:

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

What is the error in this code?

medium

A. It visits right subtree before left subtree

B. It visits left subtree before root, so not preorder

C. It does not check for null root

D. It prints node values incorrectly

Solution

1. Step 1: Analyze the visiting order in the method

   The method calls Preorder on left child first, then prints root value, then calls Preorder on right child.

2. Step 2: Compare with preorder definition

   Preorder requires visiting root first, then left, then right. This code visits left subtree before root, so it is actually inorder traversal.

3. Final Answer:

   It visits left subtree before root, so not preorder -> Option B

4. Quick Check:

   Preorder must print root before children [OK]

Hint: Print root value before recursive calls for preorder [OK]

Common Mistakes:

• Printing after left subtree call instead of before
• Confusing preorder with inorder traversal
• Missing null check (though present here)

5. You want to collect all node values of a binary tree in preorder traversal into a list in C#. Which code snippet correctly does this?

hard

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

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

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

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

Solution

1. Step 1: Understand preorder traversal collection

   Preorder means visit root first, so add root value to list before recursive calls.

2. Step 2: Check order of recursive calls

   After adding root, recursively traverse left subtree, then right subtree.

3. Final Answer:

   Code snippet that adds root value first, then left, then right -> Option A

4. Quick Check:

   Preorder = Add root, then left, then right [OK]

Hint: Add root value before recursive calls for preorder list [OK]

Common Mistakes:

• Adding node value after left subtree call (inorder)
• Adding node value after both subtree calls (postorder)
• Swapping left and right subtree calls