Python Program to Implement a Binary Search Tree
Intermediate Data structures Time O(h) Space O(n)
Builds a binary search tree, where smaller values go left and larger ones right, then searches it and lists its values in sorted order.
A binary search tree (BST) is a binary tree with one rule: every value in a node's left subtree is smaller than the node's value, and every value in its right subtree is larger or equal. The rule makes searching quick: as in a binary search of a sorted list, each comparison rules out a whole side of what's left.
Inserting 50, 30, 70, 20, 40, 60 and 80, in that order, builds this tree:
50
/ \
30 70
/ \ / \
20 40 60 80To find 60, start at 50: 60 is larger, so go right to 70; 60 is smaller, so go left, and there it is, after three nodes. Reading the tree in order (left subtree, node, right subtree) gives its values sorted.
Program
class Node:
"""A value with a left and a right subtree."""
def __init__(self, value):
self.value = value
self.left = None # smaller values
self.right = None # larger or equal values
def insert(node, value):
"""Add value to the tree; return the tree's root."""
if node is None:
return Node(value)
if value < node.value:
node.left = insert(node.left, value)
else:
node.right = insert(node.right, value)
return node
def search(node, value):
"""True if value is in the tree under node."""
while node:
if value == node.value:
return True
node = node.left if value < node.value else node.right
return False
def in_order(node, values):
"""Add the tree's values to values, smallest first."""
if node:
in_order(node.left, values)
values.append(node.value)
in_order(node.right, values)
return values
root = None
for value in [50, 30, 70, 20, 40, 60, 80]:
root = insert(root, value)
print("Sorted:", in_order(root, []))
print("Has 60:", search(root, 60))
print("Has 65:", search(root, 65))
Open in the editor Download binary_search_tree.py
Output
Sorted: [20, 30, 40, 50, 60, 70, 80]
Has 60: True
Has 65: False
How it works
Step through the program line by line: each step below shows up as its line runs.
- A
Nodeholds a value and two subtrees:leftfor smaller values andrightfor larger or equal ones. Both start empty (None). -
insert()is recursive. When it reaches an empty place, the value goes there, in a new node. - Otherwise a smaller value goes into the left subtree and any other value into the right.
Each call returns the root of its subtree, which is how the new node gets linked to its parent: the parent stores
the result in
node.leftornode.right. For a subtree that was already there, that stores the same node again. -
search()starts at the root and goes down one level each time round the loop. It returnsTruewhen it finds the value, and otherwise moves left if the value is smaller or right if it's larger. Falling off the bottom of the tree (None) means the value isn't in it. -
in_order()adds the left subtree's values, then the node's, then the right subtree's. Because of the tree's rule, that's smallest to largest. - The program starts with an empty tree and inserts seven values.
rootis set from each call, but it changes only on the first, when the tree was empty. - It prints the values in order, then searches for 60, which is in the tree, and 65, which isn't.
Searching for 65:
| Step | node | Compare | Then |
|---|---|---|---|
| 1 | 50 | 65 > 50 | go right |
| 2 | 70 | 65 < 70 | go left |
| 3 | 60 | 65 > 60 | go right |
| 4 | None |
return False |
Time and space complexity
| Time | O(h) |
|---|---|
| Extra space | O(n) |
| Operation | Time |
|---|---|
insert() |
O(h) |
search() |
O(h) |
in_order() |
O(n) |
h is the tree's height, how many levels it has. Insert and search go down one level per step, so they take at most h steps. A balanced tree of n values is about log₂ n levels tall: the seven values here make 3 levels, and a million would make about 20. But values inserted in sorted order, such as 10, 20, 30, 40, each go to the right of the one before, and the tree becomes a chain with h = n. Searching it is then no faster than checking a list item by item: O(n). Self-balancing trees, such as AVL and red-black trees, rearrange their nodes to keep h close to log₂ n.
in_order() visits every node once: O(n). The tree takes O(n) space, one node per value. The recursive insert() and
in_order() calls use O(h) more for the calls in progress, while search() uses a loop and needs O(1).
Other ways to write it
Searching with recursion
search() can have the same shape as insert(): each call checks one node and searches one of its subtrees.
class Node:
def __init__(self, value, left=None, right=None):
self.value, self.left, self.right = value, left, right
def search(node, value):
if node is None:
return False
if value == node.value:
return True
if value < node.value:
return search(node.left, value)
return search(node.right, value)
root = Node(50, Node(30, Node(20), Node(40)),
Node(70, Node(60), Node(80)))
print(search(root, 60), search(root, 65))A sorted list with bisect
Python's standard library has no tree, but a list kept sorted with bisect.insort() does the same job for a few
thousand values. Searching it is O(log n), though each insert moves the larger items along: O(n).
from bisect import bisect_left, insort
def contains(items, value):
index = bisect_left(items, value)
return index < len(items) and items[index] == value
values = []
for value in [50, 30, 70, 20, 40, 60, 80]:
insort(values, value)
print(values, contains(values, 60), contains(values, 65))Try it yourself
- Search for 20 and 80, the smallest and largest values, and for 10 and 90, which are outside the tree.
- Write
minimum(node): the smallest value is at the end of the left links, so follow them until there are no more. - Insert 50 a second time. Where does it go, and where does it show up in the sorted list?
- Write
height(node): 0 forNone, otherwise 1 more than the taller subtree. It's 3 here. Insert the same values in sorted order,[20, 30, 40, 50, 60, 70, 80], and it's 7.