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.