The BST Rule, Search and Insert

28 min · Intermediate

A list can be searched fast only if it is sorted, and a sorted list is slow to insert into. A binary search tree keeps keys in order in a different way: every comparison throws away a whole side, and adding a key does not move the others.

What a binary search tree is

Binary search tree (BST) is a tree where every key in a node's left subtree is smaller than the node's key and every key in its right subtree is larger. This course uses distinct keys.

A tree stores items in nodes. Each node holds a key and points to at most two children, a left one and a right one. One rule about the keys makes lookups fast.

Python

class Node:    def __init__(self, key):        self.key = key        self.left = None        self.right = None

None means there is no child on that side. A subtree is a node together with everything below it.

Search: pick a side at every node

To find 7, start at the root 8. 7 is smaller, so it can only be in the left subtree. Move there and repeat. Each step drops a whole side, like binary search on a list.

Python

def search(node, key):    while node is not None and node.key != key:        node = node.left if key < node.key else node.right    return node is not None

Example 1 · Follow the search path

Python

1class Node:2    def __init__(self, key):3        self.key = key4        self.left = None5        self.right = None6
7def insert(node, key):8    if node is None:9        return Node(key)10    if key < node.key:11        node.left = insert(node.left, key)12    elif key > node.key:13        node.right = insert(node.right, key)14    return node15
16root = None17for key in [8, 3, 10, 1, 6, 14, 4, 7, 13]:18    root = insert(root, key)19node = root20path = []21while node is not None:22    path.append(node.key)23    if node.key == 7:24        break25    node = node.left if 7 < node.key else node.right26print(path)

Output

[8, 3, 6, 7]

What this code does

The tree was built by inserting 8, 3, 10, 1, 6, 14, 4, 7, 13 in that order.
Only four of the nine nodes are visited. The other five were never touched.

Example 2 · A key that is not there

Python

1class Node:2    def __init__(self, key):3        self.key = key4        self.left = None5        self.right = None6
7def insert(node, key):8    if node is None:9        return Node(key)10    if key < node.key:11        node.left = insert(node.left, key)12    elif key > node.key:13        node.right = insert(node.right, key)14    return node15
16def search(node, key):17    while node is not None and node.key != key:18        node = node.left if key < node.key else node.right19    return node is not None20
21root = None22for key in [8, 3, 10, 1, 6, 14, 4, 7, 13]:23    root = insert(root, key)24print(search(root, 5))25print(search(root, 13))26print(search(None, 1))

Output

False
True
False

What this code does

5 would sit under 4 on the right. That child is None, so the loop stops and returns False.
An empty tree is just None, and search handles it with no special case.

The loop ends when the key is found or a child is None. It visits one node per level, so the time is O(h) for height h, and the space is O(1).

Insert: search, then attach

To add a key, follow the search path until a child is missing and put the new node there. Old nodes never move. A key that is already present is ignored.

Python

1def insert(node, key):2    if node is None:3        return Node(key)4    if key < node.key:5        node.left = insert(node.left, key)6    elif key > node.key:7        node.right = insert(node.right, key)8    return node

Example 3 · Where a new key attaches

Python

1class Node:2    def __init__(self, key):3        self.key = key4        self.left = None5        self.right = None6
7def insert(node, key):8    if node is None:9        return Node(key)10    if key < node.key:11        node.left = insert(node.left, key)12    elif key > node.key:13        node.right = insert(node.right, key)14    return node15
16root = None17for key in [8, 3, 10, 1, 6, 14, 4, 7, 13]:18    root = insert(root, key)19node = root20path = []21while True:22    path.append(node.key)23    child = node.left if 5 < node.key else node.right24    if child is None:25        break26    node = child27print(path)28root = insert(root, 5)29print(node.right.key)

Output

[8, 3, 6, 4]
5

What this code does

The search for 5 ends at 4, which has no right child. Insert hangs 5 there.
The same path decides both the search and the insert.

node.left = insert(node.left, key) returns the child, new or old, so the parent always points to the right node. Write root = insert(root, key), because the root changes when the tree is empty.

The height decides the cost

Height of a tree is the number of nodes on the longest path from the root to a leaf. An empty tree has height 0. Search and insert in a BST take O(h) time.

Height is the number of nodes on the longest path from the root down. Search and insert take O(h) steps. The same keys can make a short tree or a long chain, depending on the order they arrive in.

Python

def height(node):    if node is None:        return 0    return 1 + max(height(node.left), height(node.right))

Example 4 · Same keys, different shape

Python

1class Node:2    def __init__(self, key):3        self.key = key4        self.left = None5        self.right = None6
7def insert(node, key):8    if node is None:9        return Node(key)10    if key < node.key:11        node.left = insert(node.left, key)12    elif key > node.key:13        node.right = insert(node.right, key)14    return node15
16def height(node):17    if node is None:18        return 019    return 1 + max(height(node.left), height(node.right))20
21balanced = None22for key in [4, 2, 6, 1, 3, 5, 7]:23    balanced = insert(balanced, key)24chain = None25for key in [1, 2, 3, 4, 5, 6, 7]:26    chain = insert(chain, key)27print(height(balanced))28print(height(chain))

Output

3
7

What this code does

Inserting the middle key first splits the keys evenly, so the height is 3.
Inserting sorted keys makes every new key a right child, so the tree is a chain of height 7 and search is no better than a list scan.

An empty tree has height 0. A single node has height 1. Recursion adds one for the current node to the taller child.

Next step

Check your understanding

12 quick questions

What a binary search tree is

Binary search tree (BST) is a tree where every key in a node's left subtree is smaller than the node's key and every key in its right subtree is larger. This course uses distinct keys.

A tree stores items in nodes. Each node holds a key and points to at most two children, a left one and a right one. One rule about the keys makes lookups fast.

1class Node:2 def __init__(self, key):3 self.key = key4 self.left = None5 self.right = None6 7def insert(node, key):8 if node is None:9 return Node(key)10 if key < node.key:11 node.left = insert(node.left, key)12 elif key > node.key:13 node.right = insert(node.right, key)14 return node15 16root = None17for key in [8, 3, 10, 1, 6, 14, 4, 7, 13]:18 root = insert(root, key)19node = root20path = []21while node is not None:22 path.append(node.key)23 if node.key == 7:24 break25 node = node.left if 7 < node.key else node.right26print(path)

1class Node:2 def __init__(self, key):3 self.key = key4 self.left = None5 self.right = None6 7def insert(node, key):8 if node is None:9 return Node(key)10 if key < node.key:11 node.left = insert(node.left, key)12 elif key > node.key:13 node.right = insert(node.right, key)14 return node15 16def search(node, key):17 while node is not None and node.key != key:18 node = node.left if key < node.key else node.right19 return node is not None20 21root = None22for key in [8, 3, 10, 1, 6, 14, 4, 7, 13]:23 root = insert(root, key)24print(search(root, 5))25print(search(root, 13))26print(search(None, 1))

1def insert(node, key):2 if node is None:3 return Node(key)4 if key < node.key:5 node.left = insert(node.left, key)6 elif key > node.key:7 node.right = insert(node.right, key)8 return node

1class Node:2 def __init__(self, key):3 self.key = key4 self.left = None5 self.right = None6 7def insert(node, key):8 if node is None:9 return Node(key)10 if key < node.key:11 node.left = insert(node.left, key)12 elif key > node.key:13 node.right = insert(node.right, key)14 return node15 16root = None17for key in [8, 3, 10, 1, 6, 14, 4, 7, 13]:18 root = insert(root, key)19node = root20path = []21while True:22 path.append(node.key)23 child = node.left if 5 < node.key else node.right24 if child is None:25 break26 node = child27print(path)28root = insert(root, 5)29print(node.right.key)

The height decides the cost

Height of a tree is the number of nodes on the longest path from the root to a leaf. An empty tree has height 0. Search and insert in a BST take O(h) time.

Height is the number of nodes on the longest path from the root down. Search and insert take O(h) steps. The same keys can make a short tree or a long chain, depending on the order they arrive in.

1class Node:2 def __init__(self, key):3 self.key = key4 self.left = None5 self.right = None6 7def insert(node, key):8 if node is None:9 return Node(key)10 if key < node.key:11 node.left = insert(node.left, key)12 elif key > node.key:13 node.right = insert(node.right, key)14 return node15 16def height(node):17 if node is None:18 return 019 return 1 + max(height(node.left), height(node.right))20 21balanced = None22for key in [4, 2, 6, 1, 3, 5, 7]:23 balanced = insert(balanced, key)24chain = None25for key in [1, 2, 3, 4, 5, 6, 7]:26 chain = insert(chain, key)27print(height(balanced))28print(height(chain))