A brief introduction to Binary Search Tree (BST) using Python

An illustration of inverted tree trunk for better understanding.

Why is it called a tree?

It’s called a “tree” because it vaguely resembles an inverted tree trunk with branches.

• The word “binary” indicates that each “node” in the tree can have at most 2 children (left or right).
• Nodes can have 0, 1 or 2 children. Nodes that do not have any children are sometimes also called “leaves”.
• The single node at the top is called the “root” node, and it typically where operations like search, insertion etc. begin.

A Binary Tree

To begin, we’ll create simple binary tree(without any of the additional properties) containing numbers as keys within nodes. Here’s an example:

#simple class representing a node within a binary tree.
class TreeNode:
    def __init__(self, key):
        self.key = key
        self.left = None
        self.right = None
#create objects representing each node of the above tree
node0 = TreeNode(3)
node1 = TreeNode(4)
node2 = TreeNode(5)
#connect the nodes by setting the .left and .right properties of the root node. And we're done! We can create a new variable tree which simply points to the root node, and use it to access all the nodes within the tree.
node0.left = node1
node0.right = node2
#Going forward, we'll use the term "tree" to refer to the root node. The term "node" can refer to any node in a tree, not necessarily the root.

Traversing a Binary Tree

A traversal refers to the process of visiting each node of a tree exactly once. Visiting a node generally refers to adding the node’s key to a list. There are three ways to traverse a binary tree and return the list of visited keys:

Inorder traversal

1. Traverse the left subtree recursively inorder.
2. Traverse the current node.
3. Traverse the right subtree recursively inorder.

Preorder traversal

1. Traverse the current node.
2. Traverse the left subtree recursively preorder.
3. Traverse the right subtree recursively preorder.

Postorder traversal

1. Traverse the left subtree recursively postorder.
2. Traverse the right subtree recursively postorder.
3. Traverse the current node.

#implementation of inorder traversal of a binary tree
def traverse_in_order(node):
    if node is None: 
        return []
    return(traverse_in_order(node.left) + 
           [node.key] + 
           traverse_in_order(node.right))

Height and Size of Binary Tree

The height/depth of a binary tree is defined as the length of the longest path from its root node to a leaf.

#computation of height/depth of a binary tree
def tree_height(node):
    if node is None:
        return 0
    return 1 + max(tree_height(node.left), tree_height(node.right))
# computation of number of nodes in a binary tree
def tree_size(node):
    if node is None:
        return 0
    return 1 + tree_size(node.left) + tree_size(node.right)

A Binary Search Tree (BST)

A binary search tree or BST is a binary tree that satisfies the following conditions:

1. The left subtree of any node only contains nodes with keys less than the node’s key
2. The right subtree of any node only contains nodes with keys greater than the node’s key

#Function to check if a binary tree is a binary search tree and to find the minimum and maximum key in a binary tree
def is_bst(node):
    if node is None:
        return True, None, None
    
    is_bst_l, min_l, max_l = is_bst(node.left)
    is_bst_r, min_r, max_r = is_bst(node.right)
    
    is_bst_node = (is_bst_l and is_bst_r and 
              (max_l is None or node.key > max_l) and 
              (min_r is None or node.key < min_r))
    
    min_key = min(remove_none([min_l, node.key, min_r]))
    max_key = max(remove_none([max_l, node.key, max_r]))
    
    print(node.key, min_key, max_key, is_bst_node)
        
    return is_bst_node, min_key, max_key

Insertion in BST

Using the BST-property to perform insertion efficiently:

1. Starting from the root node, compare the key to be inserted with the current node’s key
2. If the key is smaller, recursively insert it in the left subtree (if it exists) or attach it as as the left child if no left subtree exists.
3. If the key is larger, recursively insert it in the right subtree (if it exists) or attach it as as the right child if no right subtree exists.

#Implementation of insertion
def insert(node, key, value):
    if node is None:
        node = BSTNode(key, value)
    elif key < node.key:
        node.left = insert(node.left, key, value)
        node.left.parent = node
    elif key > node.key:
        node.right = insert(node.right, key, value)
        node.right.parent = node
    return node

Finding a particular node in BST

#Implementation of finding a node
def find(node, key):
    if node is None:
        return None
    if key == node.key:
        return node
    if key < node.key:
        return find(node.left, key)
    if key > node.key:
        return find(node.right, key)

Updating value in BST

#Implementation of update
def update(node, key, value):
    target = find(node, key)
    if target is not None:
        target.value = value

Retrieving all the key-value pairs stored in BST in sorted order of keys

def list_all(node):
    if node is None:
        return []
    return list_all(node.left) + [(node.key, node.value)] + list_all(node.right)

Applications of Binary Search Trees (BSTs)

BSTs are used for a lot of applications due to its ordered structure.

• BSTs are used for indexing and multi-level indexing.
• They are also helpful to implement various searching algorithms.
• It is helpful in maintaining a sorted stream of data.
• TreeMap and TreeSet data structures are internally implemented using self-balancing BSTs.