Editor

Python Program to Implement a Binary Search Tree

Intermediate · Data structures

A binary search tree (BST) is a tree of nodes where each node has up to two children, every value in its left branch is smaller and every value in its right branch is bigger. That rule makes searching fast, because each comparison rules out a whole branch. This program inserts values, searches for some, and walks the tree in order, which lists the values sorted.

Program

binary_search_tree.py
class Node:
def __init__(self, key):
self.key = key
self.left = None # smaller keys go to the left
self.right = None # bigger keys go to the right
def insert(root, key):
if root is None: # an empty spot: the new node goes here
return Node(key)
if key < root.key:
root.left = insert(root.left, key)
elif key > root.key:
root.right = insert(root.right, key)
return root # an equal key is not added twice
def search(root, key):
if root is None:
return False # fell off the tree: the key is not there
if key == root.key:
return True
if key < root.key:
return search(root.left, key)
return search(root.right, key)
def in_order(root, result):
# The left branch, then the node, then the right branch
if root is not None:
in_order(root.left, result)
result.append(root.key)
in_order(root.right, result)
return result
root = None # an empty tree
print("Empty tree in order:", in_order(root, []))
for key in [50, 30, 70, 20, 40, 60, 80]:
root = insert(root, key)
print("In-order traversal:", in_order(root, []))
for key in [60, 25]:
print("Search", key, "->", "found" if search(root, key) else "not found")
Output
Empty tree in order: []
In-order traversal: [20, 30, 40, 50, 60, 70, 80]
Search 60 -> found
Search 25 -> not found

How it works

  1. Each Node has a key and two links, left and right, and an empty tree is just root = None.
  2. insert() starts at the root and goes left for a smaller key or right for a bigger one until it reaches an empty spot, where it puts the new node.
  3. search() follows the same path, and reaching None means the key is not there, so 25 is reported missing after comparing it with only 50, 30 and 20.
  4. in_order() visits the left branch, then the node, then the right branch, which always gives the keys in sorted order.
  5. All three functions are recursive, because the left and right branches are smaller trees that the same function can handle.

Another way to write it

Printing the tree sideways

Printing the tree sideways
class Node:
def __init__(self, key):
self.key, self.left, self.right = key, None, None
def insert(root, key):
if root is None:
return Node(key)
if key < root.key:
root.left = insert(root.left, key)
else:
root.right = insert(root.right, key)
return root
def show(node, depth=0):
if node is not None:
show(node.right, depth + 1)
print(" " * depth + str(node.key))
show(node.left, depth + 1)
root = None
for key in [50, 30, 70, 20, 40, 60, 80]:
root = insert(root, key)
show(root)
Output
        80
    70
        60
50
        40
    30
        20

Printing the right branch, then the node, then the left branch, with 4 spaces of indent per level, draws the tree on its side: tilt your head to the left and the root, 50, is at the top.

Try it yourself

Add a function that finds the smallest key by following left links until there are none.

Edit the program above and press Run, or open it in the full editor to save it and share it. To watch it run line by line, open it in the visualizer.

Related programs

All Python programs · CBSE class 12 practical file · Python exercises