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

Concept Flow - Tree Traversal Preorder Root Left Right

Start at Root

↓

Visit Node (Root)

↓

Traverse Left Subtree

↓

Traverse Right Subtree

↓

Done

Start at the root node, visit it, then recursively traverse the left subtree, followed by the right subtree.

Execution Sample

DSA Python

class Node:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

def preorder(root):
    if root:
        print(root.val)
        preorder(root.left)
        preorder(root.right)

This code visits 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	None	current = None	A ├─ B │ ├─ D │ └─ E └─ C
8	Return from None	None	return	A ├─ B │ ├─ D │ └─ E └─ C
9	Traverse right subtree	None	current = None	A ├─ B │ ├─ D │ └─ E └─ C
10	Return from None	None	return	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	None	current = None	A ├─ B │ ├─ D │ └─ E └─ C
14	Return from None	None	return	A ├─ B │ ├─ D │ └─ E └─ C
15	Traverse right subtree	None	current = None	A ├─ B │ ├─ D │ └─ E └─ C
16	Return from None	None	return	A ├─ B │ ├─ D │ └─ E └─ C
17	Return from B subtree	B	return	A ├─ B │ ├─ D │ └─ E └─ C
18	Traverse right subtree	C	current = C	A ├─ B │ ├─ D │ └─ E └─ C └─ F
19	Visit node	C	print C	A ├─ B │ ├─ D │ └─ E └─ C └─ F
20	Traverse left subtree	None	current = None	A ├─ B │ ├─ D │ └─ E └─ C └─ F
21	Return from None	None	return	A ├─ B │ ├─ D │ └─ E └─ C └─ F
22	Traverse right subtree	F	current = F	A ├─ B │ ├─ D │ └─ E └─ C └─ F
23	Visit node	F	print F	A ├─ B │ ├─ D │ └─ E └─ C └─ F
24	Traverse left subtree	None	current = None	A ├─ B │ ├─ D │ └─ E └─ C └─ F
25	Return from None	None	return	A ├─ B │ ├─ D │ └─ E └─ C └─ F
26	Traverse right subtree	None	current = None	A ├─ B │ ├─ D │ └─ E └─ C └─ F
27	Return from None	None	return	A ├─ B │ ├─ D │ └─ E └─ C └─ F
28	Return from C subtree	C	return	A ├─ B │ ├─ D │ └─ E └─ C └─ F
29	Return from root	A	return	A ├─ B │ ├─ D │ └─ E └─ C └─ F

💡 All nodes visited in preorder: root, left subtree, right subtree; recursion ends when nodes are None.

Variable Tracker

Variable	Start	After Step 1	After Step 3	After Step 5	After Step 11	After Step 18	After Step 22	Final
current	None	A	B	D	E	C	F	None
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]

Key Moments - 3 Insights

Why do we visit the node before traversing its children?

Because preorder means Root-Left-Right, so visiting the node first matches the order shown in execution_table rows 2, 4, 6, 12, 19, 23.

What happens when the current node is None?

The function returns immediately without visiting or traversing further, as seen in steps 7-10 and similar steps, ending that branch of recursion.

Why do we return after traversing left subtree before going to right subtree?

Because preorder traversal fully explores the left subtree before moving to the right, shown by returning from left subtree at step 17 before starting right subtree at step 18.

Visual Quiz - 3 Questions

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

A C

B D

C E

D F

💡 Hint

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

At which step does the traversal move from left subtree to right subtree of the root?

A Step 18

B Step 17

C Step 19

D Step 29

💡 Hint

Look for the step where 'Operation' changes to 'Traverse right subtree' with node C.

If the node E had a left child, how would the execution_table change after step 11?

A The traversal would visit E's right child before left child.

B There would be additional steps visiting E's left child before moving to E's right subtree.

C The traversal would skip E's left child and go directly to right subtree.

D No change, because preorder only visits root nodes.

💡 Hint

Preorder visits root, then left subtree, then right subtree, so left child of E would be visited before right subtree.

Concept Snapshot

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

Full Transcript

Preorder traversal visits the root node first, then recursively visits the left subtree, followed by the right subtree. The code starts at the root, prints its value, then calls itself on the left child, and then on the right child. When a node is None, the function returns immediately. This process continues until all nodes are visited in the order: root, left subtree, right subtree. The execution table shows each step, including visiting nodes and returning from None nodes. The variable tracker shows how the current node and visited nodes list change over time.

Practice

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

easy

A. Right, Root, Left

B. Left, Root, Right

C. Root, Left, Right

D. Left, Right, Root

Solution

1. Step 1: Understand preorder traversal definition

   Preorder traversal means visiting 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 as defined.

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

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

easy

A. def preorder(root):

B. def preorder_traversal():

C. def preorder(root, left, right):

D. def preorder(root, node):

Solution

1. Step 1: Identify function parameters for preorder traversal

   The function needs the root node to start traversal, so it should accept one parameter named root.

2. Step 2: Check options for correct syntax

   def preorder(root): defines a function with one parameter root, which is correct and simple for preorder traversal.

3. Final Answer:

   def preorder(root): -> Option A

4. Quick Check:

   Function header with root parameter [OK]

Hint: Preorder function usually takes only the root node [OK]

Common Mistakes:

• Adding unnecessary parameters
• Missing the root parameter
• Incorrect function syntax

3. Given the binary tree:

    1
   / \
  2   3
 / \
4   5

What is the output of the preorder traversal?

medium

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

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

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

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

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

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

3. Step 3: Traverse right subtree of 1

   Visit 3 last.

4. Final Answer:

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

5. Quick Check:

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

Hint: Visit root first, then left subtree, then right subtree [OK]

Common Mistakes:

• Visiting left subtree before root
• Swapping left and right children
• Confusing preorder with inorder or postorder

4. Consider this preorder traversal function:

def preorder(root):
    if root is None:
        return
    print(root.val)
    preorder(root.right)
    preorder(root.left)

What is the error in this code?

medium

A. It misses printing the root node

B. It does not check if root is None

C. It prints node values twice

D. It visits right subtree before left subtree, reversing preorder order

Solution

1. Step 1: Analyze the order of recursive calls

   The function calls preorder on root.right before root.left, which reverses the expected left-right order.

2. Step 2: Understand preorder traversal order

   Preorder must visit root, then left subtree, then right subtree. This code visits right subtree before left subtree, which is incorrect.

3. Final Answer:

   It visits right subtree before left subtree, reversing preorder order -> Option D

4. Quick Check:

   Left subtree must come before right in preorder [OK]

Hint: Left subtree must be visited before right in preorder [OK]

Common Mistakes:

• Swapping left and right recursive calls
• Forgetting base case check
• Printing nodes multiple times

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

hard

A. def preorder(root):
if root is None:
return []
return [root.val] + preorder(root.left) + preorder(root.right)

B. def preorder(root):
result = []
if root:
preorder(root.left)
result.append(root.val)
preorder(root.right)
return result

C. def preorder(root):
result = []
if root:
result.append(root.val)
result.extend(preorder(root.left))
result.extend(preorder(root.right))
return result

D. def preorder(root):
if root is None:
return []
return preorder(root.left) + [root.val] + preorder(root.right)

Solution

1. Step 1: Understand preorder traversal collection

   Preorder visits root first, then left subtree, then right subtree. We must collect values in this order.

2. Step 2: Analyze each option's return order

   def preorder(root): if root is None: return [] return [root.val] + preorder(root.left) + preorder(root.right) returns [root.val] + preorder(left) + preorder(right), which matches preorder order correctly.

3. Step 3: Identify errors in other options

   def preorder(root): result = [] if root: result.append(root.val) result.extend(preorder(root.left)) result.extend(preorder(root.right)) return result uses result list but calls preorder recursively without passing result, causing empty lists. def preorder(root): result = [] if root: preorder(root.left) result.append(root.val) preorder(root.right) return result appends root after left subtree, which is inorder. def preorder(root): if root is None: return [] return preorder(root.left) + [root.val] + preorder(root.right) places root.val between left and right, which is inorder.

4. Final Answer:

   def preorder(root): if root is None: return [] return [root.val] + preorder(root.left) + preorder(root.right) -> Option A

5. Quick Check:

   Preorder = root + left + right [OK]

Hint: Return root value first, then left and right lists concatenated [OK]

Common Mistakes:

• Appending root after left subtree (inorder)
• Not returning combined list properly
• Using mutable list without passing it recursively