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

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

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

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

Hint

Simply call inorder(root) to start the traversal.

Practice

1. What is the main result of performing an inorder traversal on a binary search tree (BST)?

easy

A. It visits nodes randomly.

B. It visits nodes in descending sorted order.

C. It visits only leaf nodes.

D. It visits nodes in ascending sorted order.

Solution

1. Step 1: Understand inorder traversal definition

   Inorder traversal visits the left child, then the node itself, then the right child.

2. Step 2: Apply inorder traversal to BST property

   Since BST nodes have smaller values on the left and larger on the right, inorder traversal visits nodes in ascending order.

3. Final Answer:

   It visits nodes in ascending sorted order. -> Option D

4. Quick Check:

   Inorder traversal = ascending order [OK]

Hint: Inorder on BST always gives sorted ascending list [OK]

Common Mistakes:

• Confusing inorder with preorder or postorder
• Thinking traversal visits nodes randomly
• Assuming it visits nodes in descending order

2. Which of the following is the correct sequence of steps in an inorder traversal of a binary tree?

easy

A. Visit left child, then node, then right child

B. Visit node, then left child, then right child

C. Visit right child, then node, then left child

D. Visit left child, then right child, then node

Solution

1. Step 1: Recall inorder traversal order

   Inorder traversal means visiting the left subtree first, then the node, then the right subtree.

2. Step 2: Match the correct sequence

   Visit left child, then node, then right child matches this order exactly: left child, node, right child.

3. Final Answer:

   Visit left child, then node, then right child -> Option A

4. Quick Check:

   Inorder = left, node, right [OK]

Hint: Inorder = left subtree, node, right subtree [OK]

Common Mistakes:

• Mixing up preorder and inorder sequences
• Visiting node before left child
• Visiting right child before node

3. Given the BST below, what is the output of an inorder traversal?

      10
     /  \
    5    15
   / \     \
  3   7     20

medium

A. [20, 15, 10, 7, 5, 3]

B. [10, 5, 3, 7, 15, 20]

C. [3, 5, 7, 10, 15, 20]

D. [5, 3, 7, 10, 15, 20]

Solution

1. Step 1: Perform inorder traversal on the BST

   Visit left subtree (3, 5, 7), then root (10), then right subtree (15, 20).

2. Step 2: Write nodes in visited order

   The order is 3, 5, 7, 10, 15, 20.

3. Final Answer:

   [3, 5, 7, 10, 15, 20] -> Option C

4. Quick Check:

   Inorder traversal output = sorted ascending list [OK]

Hint: Inorder traversal of BST = sorted ascending values [OK]

Common Mistakes:

• Listing nodes in preorder or postorder instead
• Confusing left and right subtree order
• Forgetting to include all nodes

4. A student wrote this inorder traversal code but it does not print nodes in sorted order for a BST. What is the mistake?

def inorder(node):
    if node:
        inorder(node.right)
        print(node.value)
        inorder(node.left)

medium

A. The function visits right child before left child, reversing order.

B. The function misses printing the node value.

C. The function does not check if node is None.

D. The function should print before visiting children.

Solution

1. Step 1: Analyze the traversal order in code

   The code visits right child first, then node, then left child, which is reverse of inorder.

2. Step 2: Understand effect on BST traversal

   This reversed order prints nodes in descending order, not ascending sorted order.

3. Final Answer:

   The function visits right child before left child, reversing order. -> Option A

4. Quick Check:

   Inorder must visit left before right [OK]

Hint: Inorder visits left child before right child [OK]

Common Mistakes:

• Swapping left and right subtree calls
• Printing node value in wrong place
• Not checking for null node

5. You have a binary tree that is not a BST. You perform an inorder traversal and get the sequence [4, 2, 5, 1, 6]. Which of the following is true?

hard

A. The tree is a BST because inorder traversal is sorted.

B. The tree is not a BST because inorder traversal is not sorted.

C. Inorder traversal always gives sorted order regardless of tree type.

D. The tree must be balanced to get this sequence.

Solution

1. Step 1: Check if inorder traversal sequence is sorted

   The sequence [4, 2, 5, 1, 6] is not in ascending order.

2. Step 2: Understand BST property and inorder traversal

   In a BST, inorder traversal always produces a sorted ascending sequence. Since this is not sorted, the tree is not a BST.

3. Final Answer:

   The tree is not a BST because inorder traversal is not sorted. -> Option B

4. Quick Check:

   Inorder sorted = BST; not sorted = not BST [OK]

Hint: Inorder sorted? Yes BST; No not BST [OK]

Common Mistakes:

• Assuming inorder always sorts any tree
• Confusing balanced tree with BST
• Ignoring order of traversal output