Inserting Nodes into a BST

The Logic of Insertion

To insert a new value into a BST, we follow these steps:

1. Start at the root node.
2. Compare the new value with the current node's value.
3. If the new value is smaller, we know it belongs in the left subtree. We move to the left child.
4. If the new value is larger, we know it belongs in the right subtree. We move to the right child.
5. We repeat this process until we try to move to a child that is None. This empty spot is the correct location for our new node. We create the new node and attach it there.

What about duplicates? A standard BST does not allow duplicate values. If we try to insert a value that already exists, we simply do nothing.

Let's look at an example. Imagine we want to insert the value 40 into the tree below.

To see this process animated, the following video provides an excellent step-by-step walkthrough of building a tree from scratch by repeatedly inserting new elements.

From Logic to Python Code

In the previous lesson, we used a Node class. Now, we'll add the insertion logic directly to this class as a method. This is good object-oriented practice, as it bundles the data (the node's value and children) with the behavior that acts on it (like adding a new child).

We will define our class as BinarySearchTreeNode and add an add_child method to it.

class BinarySearchTreeNode:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

    def add_child(self, data):



        # 1. Handle duplicates: if the value already exists, do nothing.
        if data == self.data:
            return




        # 2. Decide to go left or right
        if data < self.data:



            # Add to the left subtree
            if self.left:



                # If a left child exists, ask it to add the data
                self.left.add_child(data)
            else:



                # If no left child, this is the spot! Create a new node.
                self.left = BinarySearchTreeNode(data)
        else: # data > self.data



            # Add to the right subtree
            if self.right:



                # If a right child exists, ask it to add the data
                self.right.add_child(data)
            else:



                # If no right child, this is the spot!
                self.right = BinarySearchTreeNode(data)

Notice the recursion here. If we need to add a value to the left subtree, and a left child already exists (self.left is not None), we simply call self.left.add_child(data). We are telling the left child's node to handle the insertion process for its own subtree. This continues until we find a node where the appropriate child is None—that's our base case, where we finally create and attach the new node.

For a guided walkthrough of implementing this method in Python, let's turn to a video resource.

Building a Complete Tree

Now that we have a method to add one child, how do we build a full tree from a list of numbers? We can create a simple helper function that initializes the root with the first element and then iterates through the rest, calling add_child for each one.

This helper function looks like this:

def build_tree(elements):



    # The first element becomes the root
    root = BinarySearchTreeNode(elements[0])




    # Loop through the rest of the elements and add them
    for i in range(1, len(elements)):
        root.add_child(elements[i])
    
    return root

Hands-On Practice

Let's combine everything into a single script. The following code includes the BinarySearchTreeNode class, the build_tree helper, and the search function from our previous lesson.

The exercise is to build a tree and then use the search function to verify that a newly inserted element can be found.

Copy this code into a file named bst_insert.py and run it.

# bst_insert.py

class BinarySearchTreeNode:
    """A node in a Binary Search Tree."""
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

    def add_child(self, data):
        """Recursively adds a new child node to the correct position."""
        if data == self.data:
            return  # Duplicate value, do nothing

        if data < self.data:



            # Add to the left
            if self.left:
                self.left.add_child(data)
            else:
                self.left = BinarySearchTreeNode(data)
        else:



            # Add to the right
            if self.right:
                self.right.add_child(data)
            else:
                self.right = BinarySearchTreeNode(data)

def build_tree(elements):
    """Builds a BST from a list of elements."""
    if not elements:
        return None
    
    root = BinarySearchTreeNode(elements[0])
    for i in range(1, len(elements)):
        root.add_child(elements[i])
    
    return root

def search(node, target):
    """A recursive function to search for a target key in a BST."""
    if node is None or node.data == target:
        return node
    
    if target > node.data:
        return search(node.right, target)
    
    return search(node.left, target)




# --- Main part of the script ---

numbers = [15, 12, 27, 7, 14, 20, 88, 23]
bst_root = build_tree(numbers)




# --- Test the insertion ---




# 1. Search for a value that we know was inserted
target1 = 23
print(f"Searching for {target1}...")
result1 = search(bst_root, target1)

if result1:
    print(f"Found node with key: {result1.data}\n")
else:
    print(f"Value {target1} not found.\n")




# 2. Search for a value that was NOT inserted
target2 = 50
print(f"Searching for {target2}...")
result2 = search(bst_root, target2)

if result2:
    print(f"Found node with key: {result2.data}\n")
else:
    print(f"Value {target2} not found.\n")

Self-Check Exercise: Before running the code, trace the add_child calls for the first few numbers in the numbers list: 15, 12, 27. Draw the small tree that results from these three insertions. Then, run the script to see the final output.

Interactive Exploration

Reading and writing code is essential, but sometimes interacting with a visual model can build intuition faster. The following resource provides an interactive visualization of a BST. You can use it to insert and remove nodes and see how the tree structure changes instantly.

Efficiency of Insertion

How fast is this insertion algorithm? The number of comparisons we need to make is equal to the depth of the insertion point. This means the time complexity is proportional to the height of the tree, or $O(h)$.

• Best Case (Balanced Tree): If the tree is well-balanced (not lopsided), its height $h$ is approximately ${\log }_{2}n$, where $n$ is the number of nodes. In this case, insertion is very fast: $O(\log n)$.
• Worst Case (Skewed Tree): If you insert numbers in sorted order (e.g., 10, 20, 30, 40...), the tree becomes a long chain, like a linked list. Its height $h$ is equal to $n$. The time complexity degrades to $O(n)$.

The following video gives an excellent intuitive explanation for why operations on a balanced tree are $O(\log n)$.

Understanding the difference between the $O(\log n)$ and $O(n)$ cases is crucial for technical interviews. It shows you understand not just how an algorithm works, but also its performance characteristics.

Conclusion

Great work! You have now mastered another fundamental BST operation. By building on your knowledge of the search algorithm, you successfully implemented insertion.

Key Takeaways:

• Inserting a new node into a BST uses the same "go left/go right" logic as searching.
• The correct position for a new node is the None location where a search for that value would end.
• The insertion logic can be implemented elegantly as a recursive method within the Node class.
• The time complexity of insertion is $O(h)$, which is $O(\log n)$ for a balanced tree but degrades to $O(n)$ for a skewed tree.

Preview of the Next Lesson:

Now that we can build a BST by inserting nodes, we need a way to visit and process every node in the tree. In the next lesson, we will explore the three most common tree traversal algorithms: in-order, pre-order, and post-order. These are essential patterns that form the basis for many other tree-based algorithms.