Tree Traversal Preorder Root Left Right in DSA Typescript - 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

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

Execution Sample

DSA Typescript

function preorder(node) {
  if (!node) return;
  console.log(node.val);
  preorder(node.left);
  preorder(node.right);
}

Prints nodes in preorder: root first, then left subtree, then right subtree.

Execution Table

Step	Operation	Node Visited	Left/Right	Tree State (Visual)
1	Visit root	A	Root	A ├─ B └─ C
2	Traverse left subtree	B	Left of A	A ├─ B │ ├─ D │ └─ E └─ C
3	Traverse left subtree	D	Left of B	A ├─ B │ ├─ D │ └─ E └─ C
4	Left child null	null	Left of D	No change
5	Right child null	null	Right of D	No change
6	Traverse right subtree	E	Right of B	A ├─ B │ ├─ D │ └─ E └─ C
7	Left child null	null	Left of E	No change
8	Right child null	null	Right of E	No change
9	Traverse right subtree	C	Right of A	A ├─ B │ ├─ D │ └─ E └─ C └─ F
10	Left child null	null	Left of C	No change
11	Traverse right subtree	F	Right of C	A ├─ B │ ├─ D │ └─ E └─ C └─ F
12	Left child null	null	Left of F	No change
13	Right child null	null	Right of F	No change
14	Traversal complete	null	None	Traversal done

💡 All nodes visited in preorder: root, left subtree, right subtree.

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 6	After Step 9	After Step 11	Final
Current Node	A	A	B	D	E	C	F	null
Call Stack	[]	[preorder(A)]	[preorder(B), preorder(A)]	[preorder(D), preorder(B), preorder(A)]	[preorder(E), preorder(B), preorder(A)]	[preorder(C), preorder(A)]	[preorder(F), preorder(C), preorder(A)]	[]
Output Sequence	[]	[A]	[A, B]	[A, B, D]	[A, B, D, E]	[A, B, D, E, C]	[A, B, D, E, C, F]	[A, B, D, E, C, F]

Key Moments - 3 Insights

Why do we print the node value before traversing left and right children?

Because preorder traversal visits the root node first, then left subtree, then right subtree, as shown in execution_table steps 1, 2, and 9.

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

The traversal calls preorder with null, which returns immediately without action, as seen in steps 4, 5, 7, 8, 10, 12, and 13.

How does the call stack change during traversal?

Each recursive call adds a function to the stack; when a node is fully processed, its call returns and is removed, shown in variable_tracker's Call Stack column.

Visual Quiz - 3 Questions

Look at the execution_table at step 3, which node is currently visited?

A Node E

B Node B

C Node D

D Node C

💡 Hint

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

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

A Step 2

B Step 9

C Step 6

D Step 11

💡 Hint

Look for 'Traverse right subtree' operation with node C in execution_table.

If node B had no left child, which step would be skipped?

A Step 4

B Step 6

C Step 3

D Step 7

💡 Hint

Step 4 is visiting left child null of D; if no left child of B, step 4 would be skipped.

Concept Snapshot

Preorder Tree Traversal:
- Visit root node first
- Recursively traverse left subtree
- Recursively traverse right subtree
- Uses recursion and call stack
- Output order: Root, Left, Right

Full Transcript

Preorder traversal visits nodes starting from the root, then left subtree, then right subtree. The code recursively visits each node, printing its value before going deeper. When a node is null, the recursion returns immediately. The call stack grows with each recursive call and shrinks as calls return. The output sequence follows the order nodes are visited.