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

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

This function prints nodes in preorder: root first, then left subtree, then right subtree.

Execution Table

Step	Operation	Node Visited	Pointer Changes	Tree State (Visual)
1	Start at root	A	Current = A	A ├─ B └─ C
2	Visit node	A	Print A	A ├─ B └─ C
3	Traverse left subtree	B	Current = B	A ├─ B └─ C
4	Visit node	B	Print B	A ├─ B └─ C
5	Traverse left subtree	D	Current = D	A ├─ B │ ├─ D │ └─ E └─ C
6	Visit node	D	Print D	A ├─ B │ ├─ D │ └─ E └─ C
7	Traverse left subtree	null	Current = null	A ├─ B │ ├─ D │ └─ E └─ C
8	Return from null	null	Back to D	A ├─ B │ ├─ D │ └─ E └─ C
9	Traverse right subtree	null	Current = null	A ├─ B │ ├─ D │ └─ E └─ C
10	Return from null	null	Back to B	A ├─ B │ ├─ D │ └─ E └─ C
11	Traverse right subtree	E	Current = E	A ├─ B │ ├─ D │ └─ E └─ C
12	Visit node	E	Print E	A ├─ B │ ├─ D │ └─ E └─ C
13	Traverse left subtree	null	Current = null	A ├─ B │ ├─ D │ └─ E └─ C
14	Return from null	null	Back to E	A ├─ B │ ├─ D │ └─ E └─ C
15	Traverse right subtree	null	Current = null	A ├─ B │ ├─ D │ └─ E └─ C
16	Return from null	null	Back to B	A ├─ B │ ├─ D │ └─ E └─ C
17	Return from B	B	Back to A	A ├─ B │ ├─ D │ └─ E └─ C
18	Traverse right subtree	C	Current = C	A ├─ B │ ├─ D │ └─ E └─ C
19	Visit node	C	Print C	A ├─ B │ ├─ D │ └─ E └─ C
20	Traverse left subtree	null	Current = null	A ├─ B │ ├─ D │ └─ E └─ C
21	Return from null	null	Back to C	A ├─ B │ ├─ D │ └─ E └─ C
22	Traverse right subtree	null	Current = null	A ├─ B │ ├─ D │ └─ E └─ C
23	Return from null	null	Back to C	A ├─ B │ ├─ D │ └─ E └─ C
24	Return from C	C	Back to A	A ├─ B │ ├─ D │ └─ E └─ C
25	Return from A	A	Traversal complete	A ├─ B │ ├─ D │ └─ E └─ C

💡 Traversal ends after visiting all nodes in preorder: root, left subtree, right subtree.

Variable Tracker

Variable	Start	After Step 1	After Step 3	After Step 5	After Step 11	After Step 18	Final
Current Node	null	A	B	D	E	C	null
Printed Nodes	[]	[A]	[A, B]	[A, B, D]	[A, B, D, E]	[A, B, D, E, C]	[A, B, D, E, C]

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, as shown in execution_table rows 2, 4, 6, 12, and 19 where the node is printed before moving to children.

What happens when the current node is null during traversal?

The function returns immediately without printing or traversing further, as seen in rows 7, 9, 13, 15, 20, and 22 where traversal returns from null nodes.

How does the traversal know when to backtrack to a parent node?

When both left and right children are null or fully visited, the traversal returns to the previous call, shown in rows like 8, 10, 14, 16, 21, 23, and 24 where it returns back up the tree.

Visual Quiz - 3 Questions

Look at the execution_table, what node is visited at Step 12?

A C

B D

C E

D B

💡 Hint

Check the 'Node Visited' column at Step 12 in the execution_table.

At which step does the traversal first return from a null node?

A Step 7

B Step 8

C Step 9

D Step 10

💡 Hint

Look for the first 'Return from null' operation in the execution_table.

If the left child of node B was null, how would the printed nodes change after Step 4?

A [A, B, E, C]

B [A, B, E, D, C]

C [A, B, D, E, C]

D [A, B, C]

💡 Hint

Refer to variable_tracker and consider skipping D if B's left child is null.

Concept Snapshot

Preorder Tree Traversal:
- Visit root node first
- Recursively traverse left subtree
- Recursively traverse right subtree
- Prints nodes in Root-Left-Right order
- Stops when all nodes visited

Full Transcript

Preorder traversal visits the root node first, then the left subtree, then the right subtree. The provided JavaScript function prints the value of each node as it visits. The execution table shows each step: starting at the root, printing it, then moving to the left child, printing it, and so on. When a null child is reached, the function returns to the previous node to continue traversal. The variable tracker shows how the current node and printed nodes change over time. Key moments clarify why nodes are printed before children, what happens at null nodes, and how backtracking works. The visual quiz tests understanding of node visits, returns from null, and effects of missing children. The snapshot summarizes preorder traversal as Root-Left-Right visiting order.

Practice

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

easy

A. Left, Right, Root

B. Left, Root, Right

C. Root, Left, Right

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: Confirm the visiting order

   The visiting order is Root, then Left child, then Right child.

3. Final Answer:

   Root, Left, Right -> Option C

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 or right child before root
• Mixing up left and right subtree order

2. Which of the following is the correct JavaScript function signature for preorder traversal of a binary tree node named root?

easy

A. function preorder(root) { if(root) { preorder(root.left); preorder(root.right); console.log(root.value); } }

B. function preorder(root) { if(root) { preorder(root.left); console.log(root.value); preorder(root.right); } }

C. function preorder(root) { if(root) { preorder(root.right); preorder(root.left); console.log(root.value); } }

D. function preorder(root) { if(root) { console.log(root.value); preorder(root.left); 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 steps

   function preorder(root) { if(root) { console.log(root.value); preorder(root.left); preorder(root.right); } } prints root value first, then recursively visits left and right children, matching preorder.

3. Final Answer:

   function preorder(root) { if(root) { console.log(root.value); preorder(root.left); preorder(root.right); } } -> Option D

4. Quick Check:

   Print root before children = function preorder(root) { if(root) { console.log(root.value); preorder(root.left); preorder(root.right); } } [OK]

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

Common Mistakes:

• Printing after visiting children (postorder)
• Swapping left and right recursive calls
• Missing base case for null root

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

    1
   / \
  2   3
 / \
4   5

Use the format: 1 -> 2 -> 4 -> 5 -> 3 -> null

medium

A. 1 -> 2 -> 4 -> 5 -> 3 -> null

B. 4 -> 2 -> 5 -> 1 -> 3 -> null

C. 2 -> 4 -> 5 -> 1 -> 3 -> null

D. 1 -> 3 -> 2 -> 4 -> 5 -> null

Solution

1. Step 1: Start at root node 1

   Visit root first: 1

2. Step 2: Traverse left subtree of 1

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

3. Step 3: Traverse right subtree of 1

   Visit 3

4. Final Answer:

   1 -> 2 -> 4 -> 5 -> 3 -> null -> Option A

5. Quick Check:

   Preorder visits root, left, right = 1 -> 2 -> 4 -> 5 -> 3 -> null [OK]

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

Common Mistakes:

• Visiting left subtree after right subtree
• Starting traversal from left child instead of root
• Confusing preorder with inorder or postorder

4. The following JavaScript code is intended to perform a preorder traversal and print node values. What is the error?

function preorder(root) {
  if (root === null) return;
  preorder(root.left);
  console.log(root.value);
  preorder(root.right);
}

medium

A. The console.log should be before the recursive calls

B. The base case should check for undefined, not null

C. The function should return a value instead of void

D. The left and right recursive calls are swapped

Solution

1. Step 1: Analyze the order of operations

   The code visits left child first, then prints root, then visits right child.

2. Step 2: Compare with preorder traversal order

   Preorder requires printing root before visiting children, so console.log should be before recursive calls.

3. Final Answer:

   The console.log should be before the recursive calls -> Option A

4. Quick Check:

   Print root first in preorder [OK]

Hint: Print root value before recursive calls in preorder [OK]

Common Mistakes:

• Printing after left subtree instead of before
• Confusing preorder with inorder traversal
• Ignoring base case for null nodes

5. You have a binary tree where some nodes have only one child. How does preorder traversal handle nodes with a missing left child?
Consider this tree:

    10
      \
      20
     /  \
   30    40

What is the preorder traversal output?

hard

A. 10 -> 40 -> 20 -> 30 -> null

B. 10 -> 20 -> 30 -> 40 -> null

C. 10 -> 20 -> 40 -> 30 -> null

D. 10 -> 30 -> 20 -> 40 -> null

Solution

1. Step 1: Visit root node 10

   Start with root: 10

2. Step 2: Check left child of 10

   Left child is missing, so skip to right child 20

3. Step 3: Visit node 20 and its children

   Visit 20, then left child 30, then right child 40

4. Final Answer:

   10 -> 20 -> 30 -> 40 -> null -> Option B

5. Quick Check:

   Preorder visits root, left (if any), right = 10 -> 20 -> 30 -> 40 -> null [OK]

Hint: Skip missing children, visit existing nodes in preorder order [OK]

Common Mistakes:

• Assuming missing left child means skip right child
• Visiting children in wrong order
• Confusing preorder with other traversals