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

Concept Flow - Tree Traversal Preorder Root Left Right

Start at Root

↓

Visit Node (Root)

↓

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 Java

void preorder(Node node) {
  if (node == null) return;
  System.out.print(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	Left/Right	Tree State
1	Visit root	A	Root	A
2	Traverse left subtree	B	Left of A	A -> B
3	Visit node	B	Left of A	A -> B
4	Traverse left subtree	D	Left of B	A -> B -> D
5	Visit node	D	Left of B	A -> B -> D
6	Traverse left subtree	null	Left of D	A -> B -> D
7	Traverse right subtree	null	Right of D	A -> B -> D
8	Traverse right subtree	E	Right of B	A -> B -> D -> E
9	Visit node	E	Right of B	A -> B -> D -> E
10	Traverse left subtree	null	Left of E	A -> B -> D -> E
11	Traverse right subtree	null	Right of E	A -> B -> D -> E
12	Traverse right subtree	C	Right of A	A -> B -> D -> E -> C
13	Visit node	C	Right of A	A -> B -> D -> E -> C
14	Traverse left subtree	F	Left of C	A -> B -> D -> E -> C -> F
15	Visit node	F	Left of C	A -> B -> D -> E -> C -> F
16	Traverse left subtree	null	Left of F	A -> B -> D -> E -> C -> F
17	Traverse right subtree	null	Right of F	A -> B -> D -> E -> C -> F
18	Traverse right subtree	G	Right of C	A -> B -> D -> E -> C -> F -> G
19	Visit node	G	Right of C	A -> B -> D -> E -> C -> F -> G
20	Traverse left subtree	null	Left of G	A -> B -> D -> E -> C -> F -> G
21	Traverse right subtree	null	Right of G	A -> B -> D -> E -> C -> F -> G
22	Done	null	None	Traversal complete: A B D E C F G

💡 All nodes visited in preorder; recursion ends when null children are reached.

Variable Tracker

Variable	Start	After Step 1	After Step 3	After Step 5	After Step 9	After Step 13	After Step 15	After Step 19	Final
Current Node	A	B	D	E	C	F	G	null	null
Visited Nodes	[]	[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, G]	[A, B, D, E, C, F, G]
Traversal Path	Start	Root visited	Left subtree of B	Right subtree of B	Right subtree of A	Left subtree of C	Right subtree of C	End	Complete

Key Moments - 3 Insights

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

Because preorder traversal means visiting the root node first, then left subtree, then right subtree, as shown in steps 1, 3, 5, 9, and 13 in the execution_table.

What happens when we reach a null child node?

The recursion stops for that path, as seen in steps 6, 7, 10, 11, 16, 17, 20, and 21 where traversal attempts to go left or right but finds null, so it returns.

How does the traversal know when it is done?

When all nodes have been visited and all recursive calls return after hitting null children, as indicated by step 22 'Done' in the execution_table.

Visual Quiz - 3 Questions

Look at the execution_table, which node is visited at step 5?

A E

B B

C D

D A

💡 Hint

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

At which step does the traversal move to the right subtree of node B?

A Step 8

B Step 6

C Step 10

D Step 12

💡 Hint

Look for 'Traverse right subtree' operation with 'Right of B' in the execution_table.

If node C had no right child, which step would be skipped?

A Step 14

B Step 18

C Step 19

D Step 22

💡 Hint

Step 18 visits the right child of C; if missing, this step would not occur.

Concept Snapshot

Preorder traversal visits nodes in this order:
1. Root node first
2. Then left subtree recursively
3. Then right subtree recursively
Use recursion or stack to implement
Visit node before children
Stops when node is null

Full Transcript

Preorder tree traversal means visiting the root node first, then the left subtree, and finally the right subtree. The code uses recursion: if the current node is null, it returns. Otherwise, it prints the node's value, then recursively visits the left child, then the right child. The execution table shows each step visiting nodes A, B, D, E, C, F, and G in that order. When a null child is reached, recursion stops for that path. The traversal ends after all nodes are visited. This method ensures the root is always processed before its children.

Practice

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

easy

A. Left, Root, Right

B. Right, Root, Left

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 Java method signatures correctly represents a preorder traversal method for a binary tree node class named Node?

easy

A. void preorderTraversal(Node root) {}

B. int preorderTraversal(Node root) {}

C. Node preorderTraversal() {}

D. void preorderTraversal() {}

Solution

1. Step 1: Identify correct method signature for preorder traversal

   Preorder traversal usually returns void and takes the root node as input to traverse the tree.

2. Step 2: Check options for matching signature

   void preorderTraversal(Node root) {} matches void return type and takes Node root as parameter, which is correct.

3. Final Answer:

   void preorderTraversal(Node root) {} -> Option A

4. Quick Check:

   Traversal method is void and takes root node [OK]

Hint: Traversal methods usually return void and take root node [OK]

Common Mistakes:

• Using return type int instead of void
• Not passing root node as parameter
• Returning Node instead of void

3. Given the following binary tree:

    1
   / \
  2   3
 / \
4   5

What is the output of a preorder traversal?

medium

A. [2, 4, 5, 1, 3]

B. [4, 2, 5, 1, 3]

C. [1, 2, 4, 5, 3]

D. [1, 3, 2, 4, 5]

Solution

1. Step 1: Start preorder traversal at root node 1

   Visit 1 first, then move to left subtree.

2. Step 2: Traverse left subtree of 1: nodes 2, 4, 5

   Visit 2, then 4 (left child), then 5 (right child).

3. Step 3: Traverse right subtree of 1: node 3

   Visit 3 last.

4. Final Answer:

   [1, 2, 4, 5, 3] -> Option C

5. Quick Check:

   Preorder = Root, Left, Right = [1, 2, 4, 5, 3] [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. Consider this Java preorder traversal method for a binary tree node class Node:

void preorder(Node root) {
  if (root == null) return;
  preorder(root.left);
  System.out.print(root.data + " ");
  preorder(root.right);
}

What is the error in this code?

medium

A. It prints nodes in inorder, not preorder

B. It causes a NullPointerException

C. It misses the right subtree

D. It prints nodes in postorder

Solution

1. Step 1: Analyze the order of operations in the method

   The method first recursively visits left subtree, then prints root data, then visits right subtree.

2. Step 2: Compare with preorder definition

   Preorder should print root first, but this code prints root after left subtree, which is inorder traversal.

3. Final Answer:

   It prints nodes in inorder, not preorder -> Option A

4. Quick Check:

   Print before left recursion for preorder [OK]

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

Common Mistakes:

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

5. You want to collect all node values of a binary tree in preorder traversal into a list in Java. Which code snippet correctly does this?

hard

A. void preorder(Node root, List<Integer> list) {
if (root == null) return;
preorder(root.left, list);
list.add(root.data);
preorder(root.right, list);
}

B. void preorder(Node root, List<Integer> list) {
if (root == null) return;
list.add(root.data);
preorder(root.left, list);
preorder(root.right, list);
}

C. void preorder(Node root, List<Integer> list) {
if (root == null) return;
preorder(root.left, list);
preorder(root.right, list);
list.add(root.data);
}

D. void preorder(Node root, List<Integer> list) {
if (root == null) return;
preorder(root.right, list);
list.add(root.data);
preorder(root.left, list);
}

Solution

1. Step 1: Understand preorder traversal order

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

2. Step 2: Check which code adds root data before recursive calls

   void preorder(Node root, List<Integer> list) { if (root == null) return; list.add(root.data); preorder(root.left, list); preorder(root.right, list); } adds root.data to list first, then recursively visits left and right subtrees, matching preorder.

3. Final Answer:

   void preorder(Node root, List<Integer> list) { if (root == null) return; list.add(root.data); preorder(root.left, list); preorder(root.right, list); } -> Option B

4. Quick Check:

   Add root before left and right recursion [OK]

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

Common Mistakes:

• Adding node data after left subtree (inorder)
• Adding node data after both subtrees (postorder)
• Visiting right subtree before left