Tree Traversal Preorder Root Left Right in DSA Python - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Preorder Traversal Output of a Simple Binary Tree

What is the output of the preorder traversal (Root, Left, Right) of the following binary tree?

Tree structure:
1
/ \ 2 3
/
4

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 []
    return [root.val] + preorder(root.left) + preorder(root.right)

root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)

result = preorder(root)
print(result)

A [1, 2, 4, 3]

B [1, 3, 2, 4]

C [4, 2, 1, 3]

D [2, 4, 1, 3]

💡 Hint

Remember preorder means visit root first, then left subtree, then right subtree.

Preorder traversal visits nodes in the order: root, left child, right child. So we visit 1, then go left to 2, then left to 4, then back up and right to 3.

❓ Predict Output

intermediate

Preorder Traversal Output with Null Children

What is the preorder traversal output of this binary tree?

Tree structure:
5
/ \ 6 None
\ 7

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 []
    return [root.val] + preorder(root.left) + preorder(root.right)

root = Node(5)
root.left = Node(6)
root.left.right = Node(7)

result = preorder(root)
print(result)

A [7, 6, 5]

B [5, 7, 6]

C [5, 6, 7]

D [6, 7, 5]

💡 Hint

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

Start at root 5, then go left to 6, then 6's right child 7. No right child of 5 exists.

🔧 Debug

advanced

Identify the Error in Preorder Traversal Implementation

What error will this preorder traversal code produce when run on a non-empty tree?

DSA Python

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

root = Node(1)
root.left = Node(2)
root.right = Node(3)
print(preorder(root))

A Output: [1, 2, 3]

B Output: [2, 3, 1]

C TypeError: unsupported operand type(s) for +: 'NoneType' and 'list'

D Output: [2, 3, 1] but this is postorder, not preorder

💡 Hint

Check the order of concatenation in the return statement.

The code visits left, then right, then root, which is postorder traversal, not preorder. The output is [2, 3, 1].

❓ Predict Output

advanced

Preorder Traversal Output of a Larger Tree

What is the preorder traversal output of this binary tree?

Tree structure:
10
/ \ > 5 15
/ \ \ > 3 7 18

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 []
    return [root.val] + preorder(root.left) + preorder(root.right)

root = Node(10)
root.left = Node(5)
root.right = Node(15)
root.left.left = Node(3)
root.left.right = Node(7)
root.right.right = Node(18)

result = preorder(root)
print(result)

A [10, 15, 18, 5, 3, 7]

B [10, 5, 3, 7, 15, 18]

C [3, 5, 7, 10, 15, 18]

D [5, 3, 7, 10, 15, 18]

💡 Hint

Remember preorder visits root first, then left subtree, then right subtree.

Visit 10 first, then left subtree (5, 3, 7), then right subtree (15, 18).

🧠 Conceptual

expert

Number of Nodes Visited in Preorder Traversal

Given a binary tree with 7 nodes, how many nodes does the preorder traversal visit?

A 7

B 6

C 8

D Depends on the tree structure

💡 Hint

Preorder traversal visits every node exactly once.

Preorder traversal visits every node in the tree exactly once, so it visits all 7 nodes.

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