Inserting into a BST

Insertion follows a simple rule: find where the value should go, then add it there. The BST property tells us exactly where.

The Algorithm

Here’s the process:

1. Start at the root
2. Compare value with current node
3. If smaller, go left; if larger, go right
4. If you reach null, that’s where it goes
5. Create a new node there

Recursive Implementation

Recursion fits this problem well. Here’s how:

Iterative Implementation

Some prefer iteration. Here’s the same logic without recursion:

Try It Yourself

Use the interactive BST builder to insert values:

Try inserting: 50, 30, 70, 20, 40, 60, 80. Watch how each value finds its correct position.

Step-by-Step Example

Let’s insert 35 into this tree:

    50
   /  \
  30   70
 / \  / \
20 40 60 80

1. Start at 50. 35 < 50, go left
2. At 30. 35 > 30, go right
3. At 40. 35 < 40, go left
4. Found null! Insert 35 here

Result:

    50
   /  \
  30   70
 / \  / \
20 40 60 80
    \
    35

Time Complexity

• Average case: O(log n) - we traverse one path from root to leaf
• Worst case: O(n) - if tree is unbalanced (like a linked list)

The average case is what makes BSTs useful. Most real-world trees stay reasonably balanced.

Common Mistakes

1. Forgetting to return the new node: In recursion, you must return the node
2. Not handling null root: Empty tree needs special handling
3. Breaking BST property: Always compare and go left/right correctly
4. Duplicate values: Decide whether to allow duplicates or ignore them

What’s Next?

Now that you can insert nodes, let’s learn how to search for values. It’s similar to insertion but simpler.