Tree Traversal Preorder Root Left Right in DSA Python - Build from Scratch

Tree Traversal Preorder Root Left Right

📖 Scenario: Imagine you have a family tree and you want to visit each family member starting from the oldest ancestor, then their children, and so on. This is like walking through a tree data structure in a specific order called preorder traversal.

🎯 Goal: You will build a simple tree using nodes and then write code to visit each node in preorder (root, left, right) order. Finally, you will print the values of the nodes in the order they are visited.

📋 What You'll Learn

Create a simple tree node class with a value and left and right children

Build a specific tree with given values

Write a preorder traversal function that visits root, then left subtree, then right subtree

Print the values of the nodes in preorder traversal order

💡 Why This Matters

🌍 Real World

Tree traversal is used in many real-world tasks like searching files in folders, organizing data, and processing hierarchical information.

💼 Career

Understanding tree traversal is important for software developers, data scientists, and anyone working with structured data or algorithms.

1

Create the Tree Node Class and Build the Tree

Create a class called TreeNode with an __init__ method that takes value, left, and right parameters. Then create the tree nodes exactly as follows: root node with value 1, left child with value 2, right child with value 3, left child of node 2 with value 4, and right child of node 2 with value 5. Assign the root node to a variable called root.

DSA Python

# Create TreeNode class and build the tree with root, left, and right nodes
# Your code here

Hint

Define the TreeNode class first. Then create nodes and link them by assigning to left and right properties.

2

Create a List to Store Preorder Traversal Result

Create an empty list called preorder_result that will store the values of nodes visited during preorder traversal.

DSA Python

class TreeNode:
    def __init__(self, value, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right

root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)

# Create an empty list called preorder_result
# Your code here

Hint

Just create an empty list named preorder_result to hold traversal values.

3

Write the Preorder Traversal Function

Write a function called preorder_traversal that takes a parameter node. Inside the function, if node is not None, append node.value to preorder_result, then recursively call preorder_traversal on node.left, and then on node.right.

DSA Python

class TreeNode:
    def __init__(self, value, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right

root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)

preorder_result = []

# Define preorder_traversal function here
# Your code here

Hint

Visit the root node first by appending its value, then visit left child, then right child recursively.

4

Run Preorder Traversal and Print the Result

Call the function preorder_traversal with root as argument. Then print the list preorder_result.

DSA Python

class TreeNode:
    def __init__(self, value, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right

root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)

preorder_result = []

def preorder_traversal(node):
    if node is not None:
        preorder_result.append(node.value)
        preorder_traversal(node.left)
        preorder_traversal(node.right)

# Call preorder_traversal with root and print preorder_result
# Your code here

Hint

Call the traversal function with root and then print the preorder_result list.

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