A binary search tree (BST) is a binary tree in which, for every node, all keys of the left subtree are smaller and all keys of the right subtree are larger. Thanks to this property search works like binary search: at each step half of the tree is discarded. For the implementation of a binary tree see the previous topic.

Searching for key `7` in a BST: `8 → 3 → 6 → 7`
Searching for key 7 in a BST: 8 → 3 → 6 → 7

The property and search

If the key is smaller than the node, go left; if larger, go right; if equal, we found it; if we reach None, the key is absent. The number of steps is bounded by the height h of the tree: O(h).

Insertion

Follow the same path as in a search and put a new leaf in place of None. A new key always becomes a leaf; existing keys do not move. In this example duplicates are rejected (insert returns False).

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

class BST:
    def __init__(self):
        self.root = None
        self.size = 0

    def insert(self, key):
        if self.root is None:
            self.root = Node(key)
            self.size = 1
            return True
        node = self.root
        while True:
            if key < node.key:
                if node.left is None:
                    node.left = Node(key)
                    break
                node = node.left
            elif key > node.key:
                if node.right is None:
                    node.right = Node(key)
                    break
                node = node.right
            else:
                return False
        self.size += 1
        return True