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

Concept Flow - Tree Traversal Preorder Root Left Right

Start at Root Node

↓

Visit Node (Process Data)

↓

Traverse Left Subtree

↓

Traverse Right Subtree

↓

Return to Parent or End

Start at the root, visit it, then recursively visit left subtree, then right subtree.

Execution Sample

DSA Go

func preorder(node *Node) {
  if node == nil {
    return
  }
  fmt.Println(node.value)
  preorder(node.left)
  preorder(node.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	Visit root	A	current = A	A ├─ B └─ C
2	Traverse left subtree	B	current = B	A ├─ B └─ C
3	Visit node	B	none	A ├─ B └─ C
4	Traverse left subtree	D	current = D	A ├─ B │ ├─ D │ └─ E └─ C
5	Visit node	D	none	A ├─ B │ ├─ D │ └─ E └─ C
6	Traverse left subtree	nil	current = nil	A ├─ B │ ├─ D │ └─ E └─ C
7	Return from nil	nil	back to D	A ├─ B │ ├─ D │ └─ E └─ C
8	Traverse right subtree	nil	current = nil	A ├─ B │ ├─ D │ └─ E └─ C
9	Return from nil	nil	back to B	A ├─ B │ ├─ D │ └─ E └─ C
10	Traverse right subtree	E	current = E	A ├─ B │ ├─ D │ └─ E └─ C
11	Visit node	E	none	A ├─ B │ ├─ D │ └─ E └─ C
12	Traverse left subtree	nil	current = nil	A ├─ B │ ├─ D │ └─ E └─ C
13	Return from nil	nil	back to E	A ├─ B │ ├─ D │ └─ E └─ C
14	Traverse right subtree	nil	current = nil	A ├─ B │ ├─ D │ └─ E └─ C
15	Return from nil	nil	back to B	A ├─ B │ ├─ D │ └─ E └─ C
16	Return from B	B	back to A	A ├─ B │ ├─ D │ └─ E └─ C
17	Traverse right subtree	C	current = C	A ├─ B │ ├─ D │ └─ E └─ C ├─ F └─ G
18	Visit node	C	none	A ├─ B │ ├─ D │ └─ E └─ C ├─ F └─ G
19	Traverse left subtree	F	current = F	A ├─ B │ ├─ D │ └─ E └─ C ├─ F └─ G
20	Visit node	F	none	A ├─ B │ ├─ D │ └─ E └─ C ├─ F └─ G
21	Traverse left subtree	nil	current = nil	A ├─ B │ ├─ D │ └─ E └─ C ├─ F └─ G
22	Return from nil	nil	back to F	A ├─ B │ ├─ D │ └─ E └─ C ├─ F └─ G
23	Traverse right subtree	nil	current = nil	A ├─ B │ ├─ D │ └─ E └─ C ├─ F └─ G
24	Return from nil	nil	back to C	A ├─ B │ ├─ D │ └─ E └─ C ├─ F └─ G
25	Traverse right subtree	G	current = G	A ├─ B │ ├─ D │ └─ E └─ C ├─ F └─ G
26	Visit node	G	none	A ├─ B │ ├─ D │ └─ E └─ C ├─ F └─ G
27	Traverse left subtree	nil	current = nil	A ├─ B │ ├─ D │ └─ E └─ C ├─ F └─ G
28	Return from nil	nil	back to G	A ├─ B │ ├─ D │ └─ E └─ C ├─ F └─ G
29	Traverse right subtree	nil	current = nil	A ├─ B │ ├─ D │ └─ E └─ C ├─ F └─ G
30	Return from nil	nil	back to C	A ├─ B │ ├─ D │ └─ E └─ C ├─ F └─ G
31	Return from C	C	back to A	A ├─ B │ ├─ D │ └─ E └─ C ├─ F └─ G
32	Return from root	A	Traversal complete	A ├─ B │ ├─ D │ └─ E └─ C ├─ F └─ G

💡 Traversal ends after visiting all nodes in preorder: A, B, D, E, C, F, G

Variable Tracker

Variable	Start	After Step 1	After Step 4	After Step 10	After Step 17	After Step 25	Final
current	nil	A	D	E	C	G	nil
visited_nodes	[]	[A]	[A, B, D]	[A, B, D, E]	[A, B, D, E, C]	[A, B, D, E, C, F, G]	[A, B, D, E, C, F, G]

Key Moments - 3 Insights

Why do we visit the node before traversing its left and right children?

Because preorder means Root-Left-Right, so visiting the node first is shown in execution_table rows 1, 3, 5, 11, 18, 20, 26 where the node is printed before moving to children.

What happens when the traversal reaches a nil (empty) child?

The function returns immediately without visiting, as shown in steps 6, 8, 12, 14, 21, 23, 27, 29 where current becomes nil and returns back to parent node.

How does the traversal know when to return to the parent node?

When both left and right children are nil or fully visited, the recursion returns to the previous call, as seen in steps 9, 15, 16, 24, 30, 31, and finally 32 when traversal ends.

Visual Quiz - 3 Questions

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

A E

B D

C B

D C

💡 Hint

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

At which step does the traversal first return from a nil child?

A Step 15

B Step 9

C Step 6

D Step 21

💡 Hint

Look for 'Return from nil' in the 'Operation' column in execution_table.

If the left child of node B was missing, how would the visited_nodes list change after step 10?

A [A, B, D, E]

B [A, B, E]

C [A, B]

D [A, B, D]

💡 Hint

Refer to variable_tracker's 'visited_nodes' and consider skipping node D.

Concept Snapshot

Preorder Traversal visits nodes in Root-Left-Right order.
Start at root, visit node, then recursively traverse left subtree, then right subtree.
If node is nil, return immediately.
Useful for copying trees or prefix expressions.
Output order example: A, B, D, E, C, F, G.

Full Transcript

Preorder tree traversal means visiting the root node first, then the left subtree, and finally the right subtree. The code visits a node by printing its value, then recursively calls itself on the left child, then on the right child. When a nil child is reached, the function returns immediately. The traversal ends after all nodes are visited in this order. This method is useful for tasks like copying a tree or evaluating prefix expressions.