Editor

Binary search tree in Python

A binary search tree keeps smaller values in the left branch and bigger ones in the right branch of every node, so inserting or finding a value only follows one path down the tree.

The arrow keys step through it. Edit the code to try your own input.

How it works

  1. Each Node holds a value and two links, left and right, which start as None.
  2. At every node, smaller values go to the left and the others go to the right.
  3. insert calls itself on node.left or node.right until it reaches an empty spot (None), and creates the new node there.
  4. Each call returns its node, so the parent links the new node in with node.left = ... or node.right = ....
  5. search follows the same rule in a loop: compare, then go left or right, until it finds the value or runs out of nodes.

What to watch

  • Watch the call stack while 6 is inserted: one frame at 8, one at 3, and one at the empty right side of 3.
  • Watch a new arrow appear each time a node is linked to its parent.
  • Watch search(root, 7) visit 8, 3 and 6, then fall off the tree at None: 7 is not there.

The code

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

def insert(node, value):
    if node is None:
        return Node(value)               # empty spot: the new node goes here
    if value < node.value:
        node.left = insert(node.left, value)
    else:
        node.right = insert(node.right, value)
    return node

def search(node, value):
    while node is not None:
        if value == node.value:
            return True
        node = node.left if value < node.value else node.right
    return False

root = None
for value in [8, 3, 10, 1, 6, 14]:
    root = insert(root, value)
print("6 found:", search(root, 6), "| 7 found:", search(root, 7))
Output
6 found: True | 7 found: False

Open it in the editor · Python Program to Implement a Binary Search Tree, explained