Binary Search Trees in Python

A binary search tree is a data structure that store data in a manner that is optimized for searching. This data structure is suitable for storing objects that have a well established order and are comparable.

A binary search tree is a binary tree in which the arrangement of the nodes satisfies the following properties:

The following figure shows a binary search tree.

If you observe the above figure, you will see that for every node, the left subtree has smaller values while the right subtree has larger values. This property makes it possible to perform efficient search operations.

Consider if we want to search for the node with a value of 7 in the tree shown in the previous figure. We would follow the path shown by the figure below.

The  search starts at the root node, at each step the value is compared with the value of the current node. If the value is smaller, the algorithm moves to the left child. If the value is larger, the algorithm moves to the right child. This process continues until the value is found or there are no more nodes to search.

The time complexity for searching in a binary search tree is O(log n), where n is the number of nodes in the tree. This is because at each step, the search space is divided in half, dramatically reducing the number of comparisons needed to find the value.

Implementing Binary Search Trees

Binary search trees are simply binary trees in which the aforementioned properties are upheld.

Python does not provide a builtin implementation of the tree data structure, users can implement trees from scratch or use third-party libraries. In this article, we will use the binarytree package to create binary trees.

The binarytree module is suitable for educational purposes, in real  applications, you may implement your own binary trees or use other third party libraries.

To install binarytree, use the following pip command.

pip install binarytree

The binarytree module provides the Node class to represent a node in a tree. To instantiate a node, we use the following syntax:

Node(value, left = None, right = None)

Create a binary search tree

from binarytree import Node

root = Node(10)
n1 = Node(6)
n2 = Node(14)
root.left = n1
root.right = n2

n3 = Node(4)
n4 = Node(8)
n1.left = n3
n1.right = n4 

print(root)
print(root.is_bst) #check whether the tree is a binary search tree

Creating the nodes manually as in above example can be very tedious especially if the tree contains a lot of nodes. We can instead use, the build() function in the module to create a binary tree from an iterable such as a list.

The build() function has the following syntax:

build(iterable)

The values in the iterable should be given in breadth-first order

from binarytree import build

values = [10, 6, 14, 4, 8, 12, 15, 3, 5, 7, 9, 11, 13]

T = build(values) #create the tree
print(T)
print(T.is_bst)

Searching for a value

To search for the node that holds a given value, we can recursively traverse through the relevant nodes.

At each node the search algorithm compares the node's value with the value to be searched. If the value being searched is equal to the node's value; the node is returned. If less; the search moves to the left child of the node. If greater; the search moves to the right child.

Implement the search algorithm

def search(n, value):
    if  value == n.value:
        return n
    elif value < n.value and n.left is not None:
        return search(n.left, value) #recur on left subtree

    elif  value > n.value and n.right is not None:
        return search(n.right, value) #recur on right subtree

    return n #unsuccessiful search

Note that in case of an unsuccessful search, we are returning the last node that was visited before the search terminated. This will prove useful when inserting a node in the tree as it indicates the position where the node should have been located if it was present.

from binarytree import build

#the implementation of search() is omitted refer to the previous section

data = [10, 6, 14, 4, 8, 12, 15, 3, 5, 7, 9, 11, 13 ]

T = build(data)
val = 13

n = search(T, val)

if n.value == val:
   print(f'found {n}')
else:
   print('No such value.')

In the above example  we used the search function to find the node with 13 as the value, the path taken by the algorithm to find the node is as illustrated below.

Consider what happens when we search for a value that does not exist. In this case the search function will return the last position where it expected to find the non-existent value.

from binarytree import build

#the implementation of search() is omitted refer to the previous section

data = [10, 6, 14, 4, 8, 12, 15, 3, 5, 7, 9, 11, 13 ]

T = build(data)
val = 8.5

n = search(T, val)

if val == n.value:
    print(f'found: {n}')
elif val < n.value:
    print(f"{val} should be placed at the left of {n.value}")
else:
    print(f"{val} should be placed at the right of {n.value}")

Inserting a value in the tree

When inserting a  value in a binary search tree, we must ensure that the binary search tree's structure is maintained so that nodes to the left of a parent node have values smaller than the parent, and all the nodes to the right have larger values.

From the previous section, we have seen that the search() function returns the place where a node should have been if it was present in the tree. We will use the method with the value to be inserted as the argument in order to get the node at which the value will be attached.

from binarytree import Node

def insert(T, val):
    parent = search(T, val)
    if val == parent.val: #the value exists in the tree
       return #do nothing
    newnode = Node(val)
    if val < parent.value: #the value is less than the parent
        parent.left = newnode 
    else:  #the value is greater than the parent
        parent.right = newnode

from binarytree import build

#implementation of search and insert() is omitte, refer to previous sections

data = [10, 6, 14, 4, 8, 12, 15, 3, 5, 7, 9, 11, 13 ]
T = build(data)

insert(T, 7.5)
insert(T, 6.5)
insert(T, 8.5)
print(T)

Resulting Properties of Binary Search Trees

One important resulting feature of binary search trees is that the inorder traversal algorithm always yields the elements in a sorted order. 

from binarytree import build

data = [10, 6, 14, 4, 8, 12, 15, 3, 5, 7, 9, 11, 13]

T = build(data)

print(*[i.value for i in T.inorder], sep = "  ")