Binary search tree: insert and delete

Recursive

A new key walks down from the root by comparisons to an empty spot; deleting has three cases: a leaf, one child, and two children (using the successor).

In a binary search tree, for every node, the keys in its left subtree are smaller and the keys in its right subtree are larger (or equal). So every operation follows a single path down from the root: at each node one comparison says whether to go left or right.

Read the full explanation ↓

Time: O(h) per operation (h = height)
Space: O(h) for the recursion
CLRS, section 12.3
Horowitz–Sahni, chapter 5
Johnsonbaugh, chapter 9

Input:

n=11 · insert 14, delete 6PDF export

Insert 14 into the tree, then delete 6, which has two children and is replaced by its successor (7).

class Node:
def __init__(self, key):
self.key = key
self.left = None
self.right = None
def bst(root, ops):
for op, key in ops:
if op == "insert":
root = insert(root, key)
else:
root = delete(root, key)
return root
def insert(node, key):
if node is None:
return Node(key)
if key < node.key:
node.left = insert(node.left, key)
else:
node.right = insert(node.right, key)
return node
def delete(node, key):
if node is None:
return None
if key < node.key:
node.left = delete(node.left, key)
elif key > node.key:
node.right = delete(node.right, key)
else:
if node.left is None:
return node.right
if node.right is None:
return node.left
succ = node.right
while succ.left is not None:
succ = succ.left
node.key = succ.key
node.right = delete(node.right, succ.key)
return node

Invariant: For every node, all keys in its left subtree are smaller and all keys in its right subtree are larger or equal.

Start

Recursion tree

Filled orange = running call · Orange outline = still on the stack · Grey = finished

Local variables

Orange = changed in this step

`root` object

key = 15
left = Node(key=6, left=Node(key=3, left=Node(key=2, left=None, right=None), right=Node(key=4, left=None, right=None)), right=Node(key=7, left=None, right=Node(key=13, left=…, right=None)))
right = Node(key=18, left=Node(key=17, left=None, right=None), right=Node(key=20, left=None, right=None))

`ops` list

('insert', 14)('delete', 6)

Call stack

bst()line 8

Step 1 of 58

How the work grows with input size

Average of 8 random graphs per n (fixed seeds). Hollow marker = the input on screen.

comparisons
current input (n=11)

Show as a table

n	comparisons
3	5.3
5	8.3
7	8
9	10.5
11	11.6
13	11.1
15	13.6

Explanation

The idea

Insert

Start at the root and go down by comparisons until you reach an empty spot (None). The new node is created right there. A repeated key goes to the right.

Delete: three cases

A leaf: a node with no children is simply removed.
One child: the child takes the node's place.
Two children: find the node's successor (the smallest key in its right subtree, that is, its leftmost node). Copy the successor's key into the node, then delete the successor itself (it has at most one child) from the right subtree.

In this recursive version every call returns the new root of its subtree, and the parent stores it in node.left or node.right, so the links fix themselves.

Cost

Each operation is O(h), where h is the height of the tree: log n for a balanced tree, n for a chain (keys inserted in sorted order). Self-balancing trees such as AVL and red-black trees keep the height at log n.

What to watch in the trace

The orange node is node in the running call, and a dashed orange ring marks a node created or changed in this step.
In "delete the root with two children", watch succ walk down to the leftmost node of the right subtree.
The "every loop round" detail level shows only the end of each insert or delete.