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++

struct Node {
  int data;
  Node* left;
  Node* right;
};

void preorder(Node* root) {
  if (!root) return;
  std::cout << 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	Pointer Changes	Visual State
1	Start at root	1	Root	1 / \ 2 3	current = root(1)	1 / \ 2 3
2	Visit node	1	Root	1 / \ 2 3	print 1	1 / \ 2 3
3	Traverse left subtree	2	Left	1 / \ 2 3	current = 2	1 / \ 2 3
4	Visit node	2	Left	1 / \ 2 3	print 2	1 / \ 2 3
5	Traverse left subtree	4	Left of 2	1 / \ 2 3 / 4	current = 4	1 / \ 2 3 / 4
6	Visit node	4	Left of 2	1 / \ 2 3 / 4	print 4	1 / \ 2 3 / 4
7	Traverse left subtree	null	Left of 4	1 / \ 2 3 / 4	current = null	1 / \ 2 3 / 4
8	Return from null	null	Left of 4	1 / \ 2 3 / 4	return	1 / \ 2 3 / 4
9	Traverse right subtree	null	Right of 4	1 / \ 2 3 / 4	current = null	1 / \ 2 3 / 4
10	Return from null	null	Right of 4	1 / \ 2 3 / 4	return	1 / \ 2 3 / 4
11	Return to node 2	2	Left	1 / \ 2 3 / 4	current = 2	1 / \ 2 3 / 4
12	Traverse right subtree	5	Right of 2	1 / \ 2 3 / \ 4 5	current = 5	1 / \ 2 3 / \ 4 5
13	Visit node	5	Right of 2	1 / \ 2 3 / \ 4 5	print 5	1 / \ 2 3 / \ 4 5
14	Traverse left subtree	null	Left of 5	1 / \ 2 3 / \ 4 5	current = null	1 / \ 2 3 / \ 4 5
15	Return from null	null	Left of 5	1 / \ 2 3 / \ 4 5	return	1 / \ 2 3 / \ 4 5
16	Traverse right subtree	null	Right of 5	1 / \ 2 3 / \ 4 5	current = null	1 / \ 2 3 / \ 4 5
17	Return from null	null	Right of 5	1 / \ 2 3 / \ 4 5	return	1 / \ 2 3 / \ 4 5
18	Return to node 1	1	Root	1 / \ 2 3 / \ 4 5	current = 1	1 / \ 2 3 / \ 4 5
19	Traverse right subtree	3	Right	1 / \ 2 3 / \ 4 5	current = 3	1 / \ 2 3 / \ 4 5
20	Visit node	3	Right	1 / \ 2 3 / \ 4 5	print 3	1 / \ 2 3 / \ 4 5
21	Traverse left subtree	null	Left of 3	1 / \ 2 3 / \ 4 5	current = null	1 / \ 2 3 / \ 4 5
22	Return from null	null	Left of 3	1 / \ 2 3 / \ 4 5	return	1 / \ 2 3 / \ 4 5
23	Traverse right subtree	null	Right of 3	1 / \ 2 3 / \ 4 5	current = null	1 / \ 2 3 / \ 4 5
24	Return from null	null	Right of 3	1 / \ 2 3 / \ 4 5	return	1 / \ 2 3 / \ 4 5
25	Traversal complete	null	None	1 / \ 2 3 / \ 4 5	return	1 / \ 2 3 / \ 4 5

💡 All nodes visited in preorder: root, left subtree, right subtree; recursion ends when null nodes reached

Variable Tracker

Variable	Start	After Step 3	After Step 12	After Step 19	Final
current	root(1)	node(2)	node(5)	node(3)	null
print_output	""	"1 2"	"1 2 4 5"	"1 2 4 5 3"	"1 2 4 5 3"

Key Moments - 3 Insights

Why do we print the node's data before traversing its children?

Because preorder traversal visits the root node first, as shown in execution_table rows 2, 4, 6, 13, and 20 where printing happens before recursive calls.

Why do we return immediately when the current node is null?

Returning on null nodes stops recursion, preventing errors and infinite loops, as seen in rows 7, 9, 14, 16, 21, and 23 where traversal returns without action.

How does the traversal know when to move from left subtree to right subtree?

After finishing left subtree traversal (returning from null), the code proceeds to right subtree calls, visible in execution_table rows 11 to 12 and 18 to 19.

Visual Quiz - 3 Questions

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

A Node 5

B Node 4

C Node 3

D Node 2

💡 Hint

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

At which step does the traversal move from left subtree of node 2 to its right subtree?

A Step 11

B Step 12

C Step 7

D Step 18

💡 Hint

Look for the step where 'Traverse right subtree' of node 2 starts in execution_table

If the tree had no right child for node 1, how would the traversal end?

A Traversal would skip left subtree

B Traversal would continue infinitely

C Traversal ends after visiting left subtree nodes

D Traversal would print only root node

💡 Hint

Refer to variable_tracker and execution_table showing traversal stops when null nodes reached

Concept Snapshot

Preorder Tree Traversal (Root, Left, Right):
- Visit root node first (print/process)
- Recursively traverse left subtree
- Recursively traverse right subtree
- Stops when node is null
- Prints nodes in root-left-right order

Full Transcript

Preorder traversal visits the root node first, then the left subtree, and finally the right subtree. The code starts at the root, prints its data, then recursively calls preorder on the left child, and then on the right child. When a null node is reached, the recursion returns immediately. This process continues until all nodes are visited in preorder sequence. The example tree with nodes 1, 2, 3, 4, and 5 is traversed in the order 1 2 4 5 3.

Practice

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

easy

A. Right, Root, Left

B. Left, Root, Right

C. Left, Right, Root

D. Root, Left, Right

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.

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 before root
• Visiting right before left

2. Which of the following C++ function signatures correctly represents a preorder traversal of a binary tree node Node*?

easy

A. void preorder(Node* root) { if(root) { cout << root->data; preorder(root->left); preorder(root->right); } }

B. void preorder(Node* root) { if(root) { preorder(root->left); preorder(root->right); cout << root->data; } }

C. void preorder(Node* root) { if(root) { preorder(root->right); cout << root->data; preorder(root->left); } }

D. void preorder(Node* root) { if(root) { preorder(root->left); cout << root->data; preorder(root->right); } }

Solution

1. Step 1: Recall preorder traversal order

   Preorder visits root first, then left subtree, then right subtree.

2. Step 2: Check function code order

   void preorder(Node* root) { if(root) { cout << root->data; preorder(root->left); preorder(root->right); } } prints root data first, then recursively visits left and right children, matching preorder.

3. Final Answer:

   void preorder(Node* root) { if(root) { cout << root->data; preorder(root->left); preorder(root->right); } } -> Option A

4. Quick Check:

   Print root first, then left, then right [OK]

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

Common Mistakes:

• Printing after recursive calls (postorder)
• Swapping left and right recursive calls
• Missing null check for root

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

      10
     /  \
    5    15
   /    /  \
  3    12  20

medium

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

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

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

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

Solution

1. Step 1: Start at root and visit nodes in preorder

   Visit root 10, then left subtree (5, then 3), then right subtree (15, then 12 and 20).

2. Step 2: Write traversal sequence

   Sequence is 10, 5, 3, 15, 12, 20.

3. Final Answer:

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

4. Quick Check:

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

Hint: Follow root, then left subtree, then right subtree order [OK]

Common Mistakes:

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

4. Identify the error in the following preorder traversal function and select the corrected version:

void preorder(Node* root) {
  if(root == nullptr) return;
  preorder(root->left);
  cout << root->data << " ";
  preorder(root->right);
}

medium

A. void preorder(Node* root) { if(root == nullptr) return; cout << root->data << " "; preorder(root->left); preorder(root->right); }

B. void preorder(Node* root) { if(root == nullptr) return; preorder(root->right); cout << root->data << " "; preorder(root->left); }

C. void preorder(Node* root) { if(root == nullptr) return; preorder(root->left); preorder(root->right); cout << root->data << " "; }

D. void preorder(Node* root) { if(root == nullptr) return; cout << root->data << " "; preorder(root->right); preorder(root->left); }

Solution

1. Step 1: Identify preorder traversal order

   Preorder visits root first, then left subtree, then right subtree.

2. Step 2: Check given function and options

   The given function prints after left subtree, which is inorder traversal. void preorder(Node* root) { if(root == nullptr) return; cout << root->data << " "; preorder(root->left); preorder(root->right); } prints root first, then left, then right, matching preorder.

3. Final Answer:

   void preorder(Node* root) { if(root == nullptr) return; cout << root->data << " "; preorder(root->left); preorder(root->right); } -> Option A

4. Quick Check:

   Print root before recursive calls for preorder [OK]

Hint: Print root data before recursive calls to fix preorder [OK]

Common Mistakes:

• Printing after left subtree (inorder)
• Swapping left and right subtree calls
• Missing null pointer check

5. You have a binary tree where some nodes have only one child. How does preorder traversal help in serializing this tree uniquely, and which sequence below represents the preorder traversal of this tree?

       8
      / \
     4   10
      \    \
       6    20

hard

A. [8, 10, 20, 4, 6]

B. [4, 6, 8, 10, 20]

C. [8, 4, 6, 10, 20]

D. [6, 4, 8, 20, 10]

Solution

1. Step 1: Understand preorder traversal for serialization

   Preorder visits root first, then left subtree, then right subtree, capturing structure including nodes with single children.

2. Step 2: Traverse given tree in preorder

   Visit 8 (root), then left subtree: 4, then 6 (right child of 4), then right subtree: 10, then 20 (right child of 10).

3. Step 3: Write traversal sequence

   Sequence is [8, 4, 6, 10, 20].

4. Final Answer:

   [8, 4, 6, 10, 20] -> Option C

5. Quick Check:

   Preorder captures root-left-right including single children [OK]

Hint: Preorder captures tree shape by visiting root before children [OK]

Common Mistakes:

• Ignoring nodes with single child
• Mixing preorder with inorder
• Visiting right subtree before left