Inorder traversal gives sorted order in Data Structures Theory - Mini Project: Build & Apply

Inorder Traversal Gives Sorted Order

📖 Scenario: You are learning about binary search trees (BSTs), a special kind of tree used to store numbers in order. You want to see how visiting the nodes in a certain way, called inorder traversal, lists the numbers from smallest to largest.

🎯 Goal: Build a simple binary search tree with exact numbers, set up a variable to hold the traversal result, perform an inorder traversal to collect the numbers in sorted order, and complete the structure to show the sorted list.

📋 What You'll Learn

Create a binary search tree with nodes containing values 4, 2, 5, 1, 3

Create a list variable called sorted_values to store traversal results

Write a recursive function called inorder that visits nodes in left-root-right order

Call the inorder function on the root node to fill sorted_values

💡 Why This Matters

🌍 Real World

Binary search trees are used in databases and search engines to quickly find and sort data.

💼 Career

Understanding tree traversals is important for software developers working with data structures, algorithms, and performance optimization.

1

Create the Binary Search Tree

Create a class called Node with attributes value, left, and right. Then create nodes with values 4, 2, 5, 1, and 3 and link them to form this BST structure: 4 is root, 2 is left child of 4, 5 is right child of 4, 1 is left child of 2, and 3 is right child of 2.

Data Structures Theory

# Define Node class and create nodes with values 4, 2, 5, 1, 3
# Link nodes to form the BST
# Your code here

Need a hint?

Start by defining a simple Node class with a constructor. Then create each node and connect them as described.

2

Create a List to Store Sorted Values

Create an empty list called sorted_values that will hold the values collected during inorder traversal.

Data Structures Theory

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

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

# Create an empty list called sorted_values
# Your code here

Need a hint?

Just create an empty list named exactly sorted_values.

3

Write the Inorder Traversal Function

Write a recursive function called inorder that takes a node parameter. If the node is not None, first call inorder on the left child, then append the node's value to sorted_values, then call inorder on the right child.

Data Structures Theory

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

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

sorted_values = []

# Define the inorder function below
# Your code here

Need a hint?

Use recursion to visit left child, then current node, then right child.

4

Call Inorder and Complete the Sorted List

Call the inorder function with root as the argument to fill sorted_values with the BST values in sorted order.

Data Structures Theory

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

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

sorted_values = []

def inorder(node):
    if node is not None:
        inorder(node.left)
        sorted_values.append(node.value)
        inorder(node.right)

# Call inorder on root to fill sorted_values
# Your code here

Need a hint?

Simply call inorder(root) to start the traversal.