Everything about binary search trees- Insertion, Deletion, searching, time complexity

8 min readJan 9, 2022

Definition

A binary search tree (BST), also called an ordered or sorted binary tree, is a rooted binary tree data structure whose internal nodes each store a key greater than all the keys in the node’s left subtree and less than those in its right subtree.

A binary tree is a type of data structure for storing data such as numbers in an organized way. Binary search trees allow binary search for fast lookup, addition and removal of data items, and can be used to implement dynamic sets and lookup tables.

The order of nodes in a BST means that each comparison skips about half of the remaining tree, so the whole lookup takes time proportional to the binary logarithm of the number of items stored in the tree. This is much better than the linear time required to find items by key in an (unsorted) array but slower than the corresponding operations on hash tables. Several variants of the binary search tree have been studied.

In [21]:

# A class to store a BST node
class Node:
    def __init__(self, data, left=None, right=None):
        self.data = data
        self.left = left
        self.right = right
# Function to perform inorder traversal on the BST
def inorder(root):
    if root is None:
        return    inorder(root.left)
    print(root.data, end=" ")
    inorder(root.right)

Operations and time complexity

Binary search trees support three main operations:

Searching: For searching, we have to traverse all elements (assuming we do breadth-first traversal). Therefore, searching in a binary tree has worst-case complexity of O(n).
Insertion: For inserting, we have to traverse all elements. Therefore, insertion in a binary tree has worst-case complexity of O(n).
Deletion: For deletion, we have to traverse all elements to find 2 (assuming we do breadth first traversal). Therefore, deletion in binary tree has worst case complexity of O(n)

The latter two possibly change the structural arrangement of the nodes in the tree, whereas the first one is a navigating and read-only operation. Other read-only operations are traversal, verification, etc.

Insertion

A new key is always inserted at the leaf. We start searching a key from the root until we hit a leaf node. Once a leaf node is found, the new node is added as a child of the leaf node.

Binary search tree (BST)In [22]:

# Recursive function to insert a key into a BST
def insert(root, key):
 
    # if the root is None, create a new node and return it
    if root is None:
        return Node(key)
 
    # if the given key is less than the root node, recur for the left subtree
    if key < root.data:
        root.left = insert(root.left, key)
 
    # if the given key is more than the root node, recur for the right subtree
    else:
        root.right = insert(root.right, key)
 
    return root
    keys = [21, 28, 14, 32, 25, 18, 11, 30, 19, 15, 23, 27]
root = None
for key in keys:
    root = insert(root, key)
    
inorder(root)11 14 15 18 19 21 23 25 27 28 30 32

Searching

Searching in a binary search tree for a specific key can be programmed recursively or iteratively.

We begin by examining the root node. If the tree is empty, the key we are searching for does not exist in the tree. Otherwise, if the key equals that of the root, the search is successful and we return the node.

If the key is less than that of the root, we search the left subtree. Similarly, if the key is greater than that of the root, we search the right subtree.

This process is repeated until the key is found or the remaining subtree is empty. If the searched key is not found after a empty subtree is reached, then the key is not present in the tree.

This algorithm searches from the tree’s root to the leaf farthest from the root in the worst-case. The search operation takes time proportional to the tree’s height. On average, binary search trees with n nodes have O(log(n)) height. However, in the worst case, binary search trees can have O(n) height (for skewed trees where all the nodes except the leaf have one and only one child) when the unbalanced tree resembles a linked list.

The space used by the call stack is also proportional to the tree’s height. The algorithm can be implemented iteratively to avoid use of extra space.

In [23]:

# Recursive function to search in a given BST (BFS)
def search(root, key, parent):
 
    # if the key is not present in the key
    if root is None:
        print('Key not found')
        return
 
    # if the key is found
    if root.data == key:
 
        if parent is None:
            print(f'The node with key {key} is root node')
        elif key < parent.data:
            print('The given key is the left node of the node with key', parent.data)
        else:
            print('The given key is the right node of the node with key', parent.data)
 
        return
 
    # if the given key is less than the root node, recur for the left subtree;
    # otherwise, recur for the right subtree
 
    if key < root.data:
        search(root.left, key, root)
    else:
        search(root.right, key, root)
 
 
search(root, 27, None)The given key is the right node of the node with key 25

In [24]:

# Iterative function to search in a given BST (DFS)
def searchIterative(root, key):
 
    # start with the root node
    curr = root
 
    # pointer to store the parent of the current node
    parent = None
 
    # traverse the tree and search for the key
    while curr and curr.data != key:
 
        # update the parent to the current node
        parent = curr
 
        # if the given key is less than the current node, go to the left subtree;
        # otherwise, go to the right subtree
        if key < curr.data:
            curr = curr.left
        else:
            curr = curr.right
 
    # if the key is not present in the key
    if curr is None:
        print('Key not found')
        return
 
    if parent is None:
        print(f'The node with key {key} is root node')
    elif key < parent.data:
        print('The given key is the left node of the node with key', parent.data)
    else:
        print('The given key is the right node of the node with key', parent.data)
 
 
searchIterative(root, 27)The given key is the right node of the node with key 25

Deletion

Here are three possible cases to consider deleting a node from BST:

Case 1: Deleting a node with no children: remove the node from the tree.

Case 2: Deleting a node with two children: call the node to be deleted N. Do not delete N. Instead, choose either its inorder successor (The smallest number in the right subtree) node or its inorder predecessor node (The biggest number in the left subtree), R. Copy the value of R to N, then recursively call delete on R until reaching one of the first two cases. If we choose the inorder successor of a node (The smallest number in the right subtree), as the right subtree is not NULL (our present case is a node with 2 children), then its inorder successor is a node with the least value in its right subtree, which will have at a maximum of 1 subtree, so deleting it would fall in one of the first 2 cases.

Case 3: Deleting a node with one child: remove the node and replace it with its child.

Broadly speaking, nodes with children are harder to delete. As with all binary trees, a node’s inorder successor is its right subtree’s leftmost child, and a node’s inorder predecessor is the left subtree’s rightmost child. In either case, this node will have zero or one child. Delete it according to one of the two simpler cases above.

In [25]:

# Helper function to find minimum value node in the subtree rooted at `curr`
def getMinimumKey(curr):
    while curr.left:
        curr = curr.left
    return curr
# Function to delete a node from a BST
def deleteNode(root, key):    # pointer to store the parent of the current node
    parent = None    # start with the root node
    curr = root    # search key in the BST and set its parent pointer
    while curr and curr.data != key:        # update the parent to the current node
        parent = curr        # if the given key is less than the current node, go to the left subtree;
        # otherwise, go to the right subtree
        if key < curr.data:
            curr = curr.left
        else:
            curr = curr.right    # return if the key is not found in the tree
    if curr is None:
        return root    # Case 1: node to be deleted has no children, i.e., it is a leaf node
    if curr.left is None and curr.right is None:        # if the node to be deleted is not a root node, then set its
        # parent left/right child to None
        if curr != root:
            if parent.left == curr:
                parent.left = None
            else:
                parent.right = None        # if the tree has only a root node, set it to None
        else:
            root = None    # Case 2: node to be deleted has two children
    elif curr.left and curr.right:        # find its inorder successor node
        successor = getMinimumKey(curr.right)        # store successor value
        val = successor.data        # recursively delete the successor. Note that the successor
        # will have at most one child (right child)
        deleteNode(root, successor.data)        # copy value of the successor to the current node
        curr.data = val    # Case 3: node to be deleted has only one child
    else:        # choose a child node
        if curr.left:
            child = curr.left
        else:
            child = curr.right        # if the node to be deleted is not a root node, set its parent
        # to its child
        if curr != root:
            if curr == parent.left:
                parent.left = child
            else:
                parent.right = child        # if the node to be deleted is a root node, then set the root to the child
        else:
            root = child    return root
root = deleteNode(root, 16)
inorder(root)11 14 15 18 19 21 23 25 27 28 30 32

Complete code: https://github.com/praharshbhatt/ds_algo_leetcode/blob/master/notes/data_structures/binary_search_tree/binary_search_tree.ipynb