Tree Traversal Preorder Root Left Right in DSA Python

Mental Model

Visit the root node first, then explore the left subtree, and finally the right subtree.

Analogy: Imagine reading a book where you first look at the title page (root), then read all pages on the left side (left subtree), and then the pages on the right side (right subtree).

    1
   / \
  2   3
 / \
4   5

Dry Run Walkthrough

Input: Tree: 1 as root, 2 as left child, 3 as right child, 4 as left child of 2, 5 as right child of 2

Goal: Print nodes in preorder: root first, then left subtree, then right subtree

Step 1: Visit root node 1

Visited: 1

Why: Start traversal at the root

Step 2: Traverse left subtree starting at node 2

Visited: 1 -> 2

Why: After root, visit left subtree

Step 3: Traverse left subtree of node 2, visit node 4

Visited: 1 -> 2 -> 4

Why: Preorder visits root of subtree before children

Step 4: Back to node 2, traverse right subtree, visit node 5

Visited: 1 -> 2 -> 4 -> 5

Why: After left child, visit right child

Step 5: Back to root 1, traverse right subtree, visit node 3

Visited: 1 -> 2 -> 4 -> 5 -> 3

Why: After left subtree, visit right subtree

Result:

1 -> 2 -> 4 -> 5 -> 3

Annotated Code

DSA Python

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

def preorder(root):
    if root is None:
        return []
    # Visit root first
    result = [root.val]
    # Traverse left subtree
    result += preorder(root.left)
    # Traverse right subtree
    result += preorder(root.right)
    return result

# Build tree from dry_run input
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)

output = preorder(root)
print(' -> '.join(map(str, output)))

if root is None: return []

stop recursion when no node

result = [root.val]

visit root node first

result += preorder(root.left)

recursively traverse left subtree

result += preorder(root.right)

recursively traverse right subtree

Output

1 -> 2 -> 4 -> 5 -> 3

Complexity Analysis

Time: O(n) because each node is visited exactly once

Space: O(n) due to recursion stack in worst case (skewed tree) and output list

vs Alternative: Compared to inorder or postorder, preorder visits nodes in a different order but has the same time and space complexity

Edge Cases

Empty tree (root is None)

Returns empty list without error

DSA Python

if root is None:
        return []

Single node tree

Returns list with single node value

DSA Python

result = [root.val]

When to Use This Pattern

When you need to process the root node before its children, especially to copy or serialize a tree, use preorder traversal.

Common Mistakes

Mistake: Visiting left or right child before the root node
Fix: Always add root value to result before recursive calls

Mistake: Not handling None nodes causing errors
Fix: Add base case to return empty list when node is None

Summary

Visits the root node first, then left subtree, then right subtree.

Use when you want to process or record the root before its children.

Remember: root first, then left, then right.

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