Tree traversals (inorder, preorder, postorder) in Data Structures Theory - Mini Project: Build & Apply

Tree traversals (inorder, preorder, postorder)

📖 Scenario: Imagine you have a family tree or an organizational chart. You want to visit each person in a specific order to learn about them. This is similar to how computers visit nodes in a tree data structure using different traversal methods.

🎯 Goal: You will build a simple representation of a binary tree and understand how to visit its nodes using inorder, preorder, and postorder traversals.

📋 What You'll Learn

Create a simple binary tree structure with nodes and their left and right children

Define variables to hold the root node and traversal results

Implement the three traversal methods: inorder, preorder, and postorder

Show the final traversal orders as lists of node values

💡 Why This Matters

🌍 Real World

Tree traversals are used in many areas like searching family trees, organizing files, and parsing expressions.

💼 Career

Understanding tree traversals is important for software developers, data scientists, and anyone working with hierarchical data.

1

Create the binary tree nodes

Create a dictionary called tree representing a binary tree with these exact nodes and children: 1 as root with left child 2 and right child 3, node 2 has left child 4 and right child 5, node 3 has no children, nodes 4 and 5 have no children. Represent each node as a key with a tuple value of (left_child, right_child), using None for no child.

Data Structures Theory

# Create the tree dictionary with nodes and their children
# Your code here

Need a hint?

Use a dictionary where each key is a node number and the value is a tuple of (left_child, right_child). Use None if a child does not exist.

2

Set the root node and prepare traversal lists

Create a variable called root and set it to 1. Also create three empty lists called inorder_result, preorder_result, and postorder_result to store traversal outputs.

Data Structures Theory

tree = {
    1: (2, 3),
    2: (4, 5),
    3: (None, None),
    4: (None, None),
    5: (None, None)
}
# Set root and create empty lists for traversal results
# Your code here

Need a hint?

Set root to the root node number. Create empty lists to collect nodes visited in each traversal.

3

Implement the traversal functions

Define three functions: inorder(node), preorder(node), and postorder(node). Each function should visit nodes recursively using the correct order and append the node value to the corresponding result list. Use the tree dictionary to get left and right children. If node is None, return immediately.

Data Structures Theory

tree = {
    1: (2, 3),
    2: (4, 5),
    3: (None, None),
    4: (None, None),
    5: (None, None)
}
root = 1
inorder_result = []
preorder_result = []
postorder_result = []

# Define inorder, preorder, and postorder functions
# Your code here

Need a hint?

Use recursion to visit left and right children in the correct order for each traversal. Append the current node to the correct list at the right time.

4

Run traversals and complete the results

Call the functions inorder(root), preorder(root), and postorder(root) to fill the result lists with the traversal orders.

Data Structures Theory

tree = {
    1: (2, 3),
    2: (4, 5),
    3: (None, None),
    4: (None, None),
    5: (None, None)
}
root = 1
inorder_result = []
preorder_result = []
postorder_result = []

def inorder(node):
    if node is None:
        return
    left, right = tree[node]
    inorder(left)
    inorder_result.append(node)
    inorder(right)

def preorder(node):
    if node is None:
        return
    left, right = tree[node]
    preorder_result.append(node)
    preorder(left)
    preorder(right)

def postorder(node):
    if node is None:
        return
    left, right = tree[node]
    postorder(left)
    postorder(right)
    postorder_result.append(node)

# Call the traversal functions with root
# Your code here

Need a hint?

Call each traversal function with the root node to fill the result lists.