Insert in a BST

Table of Contents +

You have a binary search tree. Now a new value arrives and you need to put it somewhere. Where does it go? You cannot just drop it anywhere. A binary search tree has one rule it must always follow. Break that rule and the tree stops working for fast search.

So inserting is not random. It is a small search. You look for the empty spot where the value belongs. Then you place it there. That is the whole idea. Let us go slow and build it.

📚 The BST Rule, One More Time

Before we insert anything, remember the rule that every node in a BST must follow.

  • Everything in the left subtree is smaller than the node.
  • Everything in the right subtree is larger than the node.

So when a new value comes in, the value itself tells you which way to go. Smaller goes left, larger goes right. You keep going down until there is no node left to compare with. That empty spot is the home for your new value.

Think of it like finding your seat in a theatre by row number. If your row is smaller than the row in front of you, you walk one way. If it is larger, you walk the other way. You stop when there are no more rows to check. You sit there.

🎯 How Insert Works

Say we already have this tree and we want to insert the value 40.

50

30

70

20

empty

60

80

Now we walk down from the top.

  • Start at 50. Is 40 smaller than 50? Yes. So go left to 30.
  • Now at 30. Is 40 smaller than 30? No, it is larger. So go right.
  • The right of 30 is empty. We found the spot. Place 40 there.

That is it. The new node 40 becomes the right child of 30. The rule still holds, because 40 is bigger than 30 and still smaller than 50. So the empty spot is always the right place for a new value.

Note

A brand new value in a BST is always added as a leaf, which is a node with no children. We never insert in the middle and push things around. We just find the empty spot and hang the new node there.

🪜 Steps to Insert a Value

Here is the plan in plain steps before we write any code.

  1. Start at the root, the top node of the tree.
  2. If the current spot is empty, this is where the new value goes. Create the node here and stop.
  3. If the new value is smaller than the current node, move to its left child.
  4. If the new value is larger than the current node, move to its right child.
  5. Repeat from step 2 until you reach an empty spot.

We will write insert using recursion, because the same job repeats on a smaller part of the tree each time. After inserting a few values, we will print an inorder traversal. That means we visit the left side, then the node, then the right side. The neat part is that an inorder walk of a BST always comes out sorted. So if our insert is correct, the printed values will be in increasing order.

💻 Code: Insert and Inorder

We will build a small BST and insert these values one by one: 50, 30, 70, 20, 40, 60, 80. Then we print the inorder traversal. If insert works, the output is sorted.

insert_bst.py
# One node of the tree
class Node:
    def __init__(self, value):
        self.data = value
        self.left = None
        self.right = None


# Insert a value and return the (possibly new) root
def insert(root, value):
    if root is None:              # empty spot found
        return Node(value)
    if value < root.data:         # smaller goes left
        root.left = insert(root.left, value)
    elif value > root.data:       # larger goes right
        root.right = insert(root.right, value)
    return root                   # equal values are ignored


# Visit left, node, right -> prints sorted
def inorder(root):
    if root is None:
        return
    inorder(root.left)
    print(root.data, end=" ")
    inorder(root.right)


root = None
values = [50, 30, 70, 20, 40, 60, 80]
for v in values:
    root = insert(root, v)


print("Inorder traversal:", end=" ")
inorder(root)
print()

The output of the above code will be:

Inorder traversal: 20 30 40 50 60 70 80

Notice the output is 20 30 40 50 60 70 80, fully sorted, even though we inserted the values in a jumbled order. That sorted line is your proof that each value landed in the correct spot.

Tip

See how the insert code does the comparing for you? You never tell it “go left” by hand. You just give it a value, and the value < root.data check decides the path. That is the BST rule doing the work.

⏱️ Time and Space Cost

Inserting means walking down one path from the root to an empty spot. The number of steps is the height of the tree, which is how many levels deep it goes.

Note

On average, a BST stays balanced and its height is about O(log n), so insert is O(log n). But if you insert already-sorted values, the tree turns into a long straight line and the height becomes O(n). Then insert slows to O(n) in the worst case.

Here is the full picture in one table.

Case Shape of Tree Time Space
Average Balanced O(log n) O(log n)
Worst Skewed (a straight line) O(n) O(n)

The space cost comes from the recursion. Each step down the tree adds one call to the call stack. So the deepest path decides the memory used.

⚠️ Common Mistakes

A few things trip people up the first time they write insert.

  • Forgetting to return the root. The recursive call gives you back the subtree’s new root. You must save it with root.left = insert(...). If you skip the assignment, your new node gets lost.
  • Not handling the empty tree. If the tree starts empty, the very first insert must create the root. The if root is None check handles this for you.
  • Allowing duplicate values without a plan. Decide early what to do with a value that already exists. Here we just ignore it. If you silently insert duplicates, your tree rule can get confusing.
  • Mixing up the comparison. Smaller goes left, larger goes right. Flip these by accident and your inorder output stops being sorted, which is the quickest way to spot the bug.

🧩 What You’ve Learned

✅ A BST insert is really a small search for the empty spot where the value belongs.

✅ Smaller values go left, larger values go right, until you reach an empty place.

✅ A new value always becomes a leaf node, so you never rearrange the existing tree.

✅ An inorder traversal of a BST prints the values in sorted order, which proves your insert is correct.

✅ Insert is O(log n) on average, but O(n) in the worst case when the tree becomes a straight line.

Check Your Knowledge

Test what you learned. Pick an answer for each question, then click Check.

  1. 1

    When inserting a value smaller than the current node, which way do you go?

    Why: In a BST, smaller values always belong in the left subtree, so you move to the left child.

  2. 2

    Where in the tree does a brand new value get placed?

    Why: Insert walks down to an empty spot and hangs the new value there as a leaf, so the existing tree is never rearranged.

  3. 3

    Why does an inorder traversal of a correct BST print sorted values?

    Why: Inorder visits the smaller left subtree first, then the node, then the larger right subtree, so values come out in increasing order.

  4. 4

    What is the worst-case time for inserting into a BST?

    Why: If values are inserted in sorted order the tree becomes a straight line of height n, making insert O(n).

Score: 0 / 4

🚀 What’s Next?

Previous Search in a BST Next Delete in a BST

Share & Connect

Share on LinkedIn