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

Concept Flow - Tree Traversal Preorder Root Left Right

Start at Root

↓

Visit Node (Root)

↓

Traverse Left Subtree

↓

Traverse Right Subtree

↓

End

Start at the root node, visit it, then recursively traverse the left subtree, followed by the right subtree.

Execution Sample

DSA C

void preorder(Node* root) {
  if (root == NULL) return;
  printf("%d ", root->data);
  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	Left/Right	Tree State
1	Visit root	1	Root	1 / \ 2 3
2	Traverse left subtree	2	Left	1 / \ 2 3
3	Visit node	2	Left	1 / \ 2 3
4	Traverse left subtree	4	Left of 2	1 / \ 2 3 / 4
5	Visit node	4	Left of 2	1 / \ 2 3 / 4
6	Traverse left subtree	NULL	Left of 4	No change
7	Traverse right subtree	NULL	Right of 4	No change
8	Traverse right subtree	5	Right of 2	1 / \ 2 3 / \ 4 5
9	Visit node	5	Right of 2	1 / \ 2 3 / \ 4 5
10	Traverse left subtree	NULL	Left of 5	No change
11	Traverse right subtree	NULL	Right of 5	No change
12	Traverse right subtree	3	Right	1 / \ 2 3 / \ 4 5
13	Visit node	3	Right	1 / \ 2 3 / \ 4 5
14	Traverse left subtree	NULL	Left of 3	No change
15	Traverse right subtree	NULL	Right of 3	No change
16	End	NULL	None	Traversal complete

💡 Traversal ends when all nodes are visited and NULL children are reached.

Variable Tracker

Variable	Start	After Step 1	After Step 3	After Step 5	After Step 9	After Step 13	Final
Current Node	1 (root)	1	2	4	5	3	NULL
Visited Nodes	[]	[1]	[1,2]	[1,2,4]	[1,2,4,5]	[1,2,4,5,3]	[1,2,4,5,3]

Key Moments - 3 Insights

Why do we visit the node before traversing its children?

Because preorder traversal means visiting the root node first, then left subtree, then right subtree, as shown in steps 1, 3, 5, 9, and 13 in the execution_table.

What happens when a node has no left or right child?

The traversal calls preorder on NULL, which immediately returns without action, as seen in steps 6, 7, 10, 11, 14, and 15 where 'NULL' nodes are reached and no changes occur.

How do we know when the traversal is complete?

When all nodes have been visited and recursive calls reach NULL children, the traversal ends, as indicated in step 16 with 'Traversal complete'.

Visual Quiz - 3 Questions

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

A Node 5

B Node 4

C Node 2

D Node 3

💡 Hint

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

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

A Step 8

B Step 3

C Step 12

D Step 16

💡 Hint

Look for 'Traverse right subtree' with node 3 in the 'Node Visited' column.

If the left subtree of node 2 was empty, which step would be skipped?

A Step 4

B Step 8

C Step 12

D Step 13

💡 Hint

Step 4 is 'Traverse left subtree' of node 2; if left child is NULL, this step would not visit a node.

Concept Snapshot

Preorder traversal visits nodes in this order:
1. Root node
2. Left subtree (preorder)
3. Right subtree (preorder)
Use recursion: visit node, then left, then right.
Stops when node is NULL.
Print or process node when visited.

Full Transcript

Preorder tree traversal means visiting the root node first, then recursively visiting the left subtree, followed by the right subtree. The provided code visits the current node, prints its data, then calls itself on the left child, then on the right child. The execution table shows each step: visiting nodes 1, 2, 4, 5, 3 in order, and returning immediately when a NULL child is reached. The variable tracker shows the current node and the list of visited nodes after each step. Key moments clarify why the node is visited before children, what happens at NULL children, and when traversal ends. The visual quiz tests understanding of node visits and traversal order. The snapshot summarizes preorder traversal as root-left-right order using recursion.

Practice

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

easy

A. Root, Left, Right

B. Left, Root, Right

C. Left, Right, Root

D. Right, Root, Left

Solution

1. Step 1: Understand preorder traversal definition

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

2. Step 2: Match the order with options

   Root, Left, Right matches the order Root, Left, Right exactly as defined.

3. Final Answer:

   Root, Left, Right -> Option A

4. Quick Check:

   Preorder = Root, Left, Right [OK]

Hint: Remember preorder starts with root node first [OK]

Common Mistakes:

• Confusing preorder with inorder or postorder
• Swapping left and right subtree order
• Thinking traversal starts with left child

2. Which of the following is the correct C syntax to start a preorder traversal function for a binary tree node named root?

easy

A. void preorder(Node root*) { if(root == NULL) return; ... }

B. void preorder(Node root) { if(root == NULL) return; ... }

C. void preorder(Node *root) { if(root == NULL) return; ... }

D. void preorder(Node *root) { if(root = NULL) return; ... }

Solution

1. Step 1: Check function parameter type

   Binary tree nodes are usually passed as pointers, so Node *root is correct.

2. Step 2: Check null pointer check syntax

   The condition if(root == NULL) correctly checks for null pointer. Assignment = is wrong.

3. Final Answer:

   void preorder(Node *root) { if(root == NULL) return; ... } -> Option C

4. Quick Check:

   Pointer param + null check == void preorder(Node *root) { if(root == NULL) return; ... } [OK]

Hint: Use pointer and '==' for null check in C [OK]

Common Mistakes:

• Passing node by value instead of pointer
• Using assignment '=' instead of comparison '=='
• Incorrect pointer syntax like 'Node root*'

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

    1
   / \
  2   3
 / \
4   5

medium

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

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

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

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

Solution

1. Step 1: Start at root node 1

   Preorder visits root first: 1

2. Step 2: Traverse left subtree of 1

   Visit 2, then left child 4, then right child 5: 2, 4, 5

3. Step 3: Traverse right subtree of 1

   Visit right child 3: 3

4. Final Answer:

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

5. Quick Check:

   Preorder = Root, Left, Right = [1,2,4,5,3] [OK]

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

Common Mistakes:

• Mixing preorder with inorder or postorder
• Visiting children before root
• Swapping left and right subtree order

4. Identify the error in this preorder traversal function and select the fix:

void preorder(Node *root) {
  if(root == NULL) return;
  preorder(root->left);
  preorder(root->right);
  printf("%d ", root->data);
}

medium

A. Add return type 'int' instead of 'void'

B. Change 'root == NULL' to 'root = NULL' in if condition

C. Remove recursive call to right subtree

D. Move printf before recursive calls to print root first

Solution

1. Step 1: Analyze traversal order in code

   Current code prints after left and right calls, which is postorder (Left, Right, Root).

2. Step 2: Fix order to preorder

   Print root data before recursive calls to get Root, Left, Right order.

3. Final Answer:

   Move printf before recursive calls to print root first -> Option D

4. Quick Check:

   Preorder prints root before children [OK]

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

Common Mistakes:

• Printing after recursive calls (postorder)
• Using assignment '=' instead of comparison '=='
• Changing return type unnecessarily

5. You want to collect all node values in preorder traversal into an array instead of printing. Which approach correctly modifies the preorder function in C?

void preorder(Node *root, int *arr, int *index) {
  if(root == NULL) return;
  // What goes here?
}

hard

A. arr[*index] = root->data; (*index)++; preorder(root->right, arr, index); preorder(root->left, arr, index);

B. arr[(*index)++] = root->data; preorder(root->left, arr, index); preorder(root->right, arr, index);

C. preorder(root->left, arr, index); preorder(root->right, arr, index); arr[(*index)++] = root->data;

D. preorder(root->left, arr, index); arr[(*index)++] = root->data; preorder(root->right, arr, index);

Solution

1. Step 1: Understand preorder traversal order

   Preorder visits root first, so store root data before recursive calls.

2. Step 2: Correctly update array and index

   Use arr[(*index)++] = root->data; to store and increment index, then recurse left and right.

3. Final Answer:

   arr[(*index)++] = root->data; preorder(root->left, arr, index); preorder(root->right, arr, index); -> Option B

4. Quick Check:

   Store root first, then left and right [OK]

Hint: Store root data before recursive calls, increment index [OK]

Common Mistakes:

• Storing data after recursive calls (not preorder)
• Incrementing index incorrectly
• Swapping left and right recursive calls