Insertion in BST in Data Structures Theory - Mini Project: Build & Apply

Insertion in BST

📖 Scenario: You are learning how to insert numbers into a Binary Search Tree (BST). A BST is a way to organize numbers so that smaller numbers go to the left and larger numbers go to the right. This helps find numbers quickly later.

🎯 Goal: Build a simple BST by inserting numbers one by one, following the BST rules.

📋 What You'll Learn

Create a node class with value, left, and right

Create a BST class with an insert method

Insert given numbers into the BST following BST rules

Show the final tree structure in code

💡 Why This Matters

🌍 Real World

BSTs are used in databases and search engines to organize data for fast searching and sorting.

💼 Career

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

1

Create the Node class

Create a class called Node with an __init__ method that takes a parameter value. Inside, set self.value = value, self.left = None, and self.right = None.

Data Structures Theory

# Create the Node class with __init__ method
# Your code here

Need a hint?

Think of a node as a box holding a number and two empty spots for smaller and larger numbers.

2

Create the BST class with root

Create a class called BST with an __init__ method that sets self.root = None.

Data Structures Theory

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

# Create the BST class with root set to None
# Your code here

Need a hint?

The BST starts empty, so the root is None at first.

3

Add the insert method to BST

Inside the BST class, create a method called insert that takes self and value. If self.root is None, set it to a new Node with value. Otherwise, call a helper method _insert_recursive with self.root and value.

Data Structures Theory

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

class BST:
    def __init__(self):
        self.root = None

# Add insert method to BST
# Your code here

Need a hint?

Start by checking if the tree is empty. If yes, the new node becomes the root.

4

Implement the _insert_recursive helper method

Inside the BST class, create a method called _insert_recursive that takes self, current_node, and value. If value is less than current_node.value, check if current_node.left is None. If yes, set it to a new Node with value. Otherwise, call _insert_recursive on current_node.left and value. If value is greater or equal, do the same on the right side.

Data Structures Theory

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

class BST:
    def __init__(self):
        self.root = None

    def insert(self, value):
        if self.root is None:
            self.root = Node(value)
        else:
            self._insert_recursive(self.root, value)

# Add _insert_recursive method to BST
# Your code here

Need a hint?

Compare the new value with the current node's value to decide left or right. Insert if empty, else go deeper.