Inserting into a BST
Finding the right spot.
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.

- 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.
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)[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.
| key | value |
|---|---|
| Leaf | just remove it |
| One child | replace with the child |
| Two children | use the next bigger value |
| Cost | O(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