AI Hints
Home›DSA in Python Tutorial›Measuring and Searching Trees
DSA in Python · Lesson 66 of 132

Inserting into a BST

Finding the right spot.

⏱ 2 min read▶ Video at 1:17:42🎓 Free
Watch this lesson in the DSA in Python courseWatch on YouTube ↗Full DSA in Python course

To insert a value into a binary search tree, you search for it. When you fall off the bottom of the tree, that empty spot is exactly where the new value belongs.

Inserting into a BST
From the video: Inserting into a BST
  • Search for the value
  • Fall off the bottom
  • That's where it goes

Building a tree

Insert is recursive. If the spot is empty, a new node goes there. Otherwise, go left for smaller values, or right for bigger ones, and attach whatever comes back. We insert seven values, then print the tree in order. Run it. The in order list is sorted, which proves the rule held.

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

def insert(root, value):
    if root is None:
        return Node(value)
    if value < root.value:
        root.left = insert(root.left, value)
    else:
        root.right = insert(root.right, value)
    return root
def in_order(n):
    return in_order(n.left) + [n.value] + in_order(n.right) if n else []
root = None
for v in [50, 30, 70, 20, 40, 60, 80]:
    root = insert(root, v)
print(in_order(root), "root:", root.value)
Output
[20, 30, 40, 50, 60, 70, 80] root: 50

Deleting, briefly

Deleting is the trickiest operation. A leaf can just be removed. A node with one child is replaced by that child. And a node with two children is replaced by the smallest value in its right subtree, which keeps the rule intact. In interviews, explaining those three cases is usually enough.

keyvalue
Leafjust remove it
One childreplace with the child
Two childrenuse the next bigger value
CostO(height)

Summary

Insert by searching, and place the new node where the search falls off. In order traversal proves the tree is sorted. Next, what happens when a tree grows lopsided.

Key takeaways
  • Search to the bottom
  • Attach the new node
  • In order is sorted
Next up: Balanced Trees — why shape matters