In this blog, you will get a deep knowledge about binary search tree, which includes creating binary search based on Linked list and various operations, like creation, inserting, deleting and searching on binary tree data structure.

What is Binary Search Tree?

The binary search tree is a binary tree with additional properties. The properties are :

In the leftsubtree, the value of a node is less than or equal to its parent node's value.
In the rightsubtree, the value of a node is greater than its parent node's value.

Visualization:

Why BST?

A binary search tree does not store an index of its data elements. Instead, it relies on implicit structure to keep a record of where each element is. For this structure, insertion and deletion of nodes can be achieved very quickly. As for traversing, in BST - only traversal of half tree is required - then we continue to other half, half of half and so on.

Create a BST

class BSTNode: 
    def __init__(self, data): 
        self.data = data 
        self.leftChild = None 
        self.rightChild = None 
newBST = BSTNode(None)

Time complexity: O(1), Space Complexity: O(1)

Insert a node to BST

In case of insertion, we have two options here :

The node could be a blank node
Binary tree has some nodes in it

The first case is easy. All we have to do is create a blank node and insert a value here.

For the 2nd case, we have to start from the root node and traverse to the left or to the right. How do we identify this? We know that, in case of BST, the left node is always smaller than the value of the right node. So, the right child is always bigger. So if the value is smaller, we'll continue left. If the value if bigger, we will continue right.

class BSTNode: 
    def __init__(self, data): 
        self.data = data 
        self.leftChild = None 
        self.rightChild = None 
    def insertNode(rootNode, nodeValue): 
        if rootNode.data == None: #O(1)
            rootNode.data = nodeValue 
        elif nodeValue <= rootNode.data: 
            if rootNode.leftChild is None: #O(1)
                rootNode.leftChild = BSTNode(nodeValue) 
            else: #O(N/2)
                insertNode(rootNode.leftChild, nodeValue)
        else: 
            if rootNode.rightChild is None: #O(1)
                rootNode.rightChild = BSTNode(nodeValue)
            else: #O(N/2)
                insertNode(rootNode.rightChild, nodeValue)
        return "The node has been successfully inserted"

newBST = BSTNode(None) 
print(insertNode(newBST, 70)) 
print(insertNode(newBST, 60))
print(newBST.data)
print(newBST.leftChild.data)

Time complexity: O(logN), Space Complexity: O(logN)

Space complexity is O(logN), when we are calling a method recursively, it's going to push a log N number of elements to the stack memory

Traverse BST

We know there are four options for traversal. (I'm not going to explain all of them, as I have detailed them in my previous blog. If you have any issues, check out the blog Tree/Binary Tree in Python DSA here.)

PreOrder Traversal: Root node -> Left subtree -> Right subtree
InOrder Traversal: Left subtree -> Root Node -> Right subtree
PostOrder Traversal : Left subtree -> Right subtree -> Root node

import QueueLinkedList as queue

class BSTNode: 
    def __init__(self, data): 
        self.data = data 
        self.leftChild = None 
        self.rightChild = None 
    def insertNode(rootNode, nodeValue): 
        if rootNode.data == None: #O(1)
            rootNode.data = nodeValue 
        elif nodeValue <= rootNode.data: 
            if rootNode.leftChild is None: #O(1)
                rootNode.leftChild = BSTNode(nodeValue) 
            else: #O(N/2)
                insertNode(rootNode.leftChild, nodeValue)
        else: 
            if rootNode.rightChild is None: #O(1)
                rootNode.rightChild = BSTNode(nodeValue)
            else: #O(N/2)
                insertNode(rootNode.rightChild, nodeValue)
        return "The node has been successfully inserted"

    def preOrderTraversal(rootNode): #O(N)
        if not rootNode: 
            return 
        print(rootNode) 
        preOrderTraversal(rootNode.leftChild) 
        preOrderTraversal(rootNode.rightChild) 

    def inOrderTraversal(rootNode): #O(N)
        if not rootNode:  #O(1)
            return 
        inOrderTraversal(rootNode.leftChild) #O(N/2)
        print(rootNode.data) #O(1)
        inOrderTraversal(rootNode.rightChild)   #O(N/2)

    def postOrderTraversal(rootNode): #O(N)
        if not rootNode:  #O(1)
            return 
        postOrderTraversal(rootNode.leftChild) #O(N/2)
        postOrderTraversal(rootNode.rightChild) #O(N/2)
        print(rootNode.data) #O(1)

    def levelOrderTraversal(rootNode): #O(N)
        if not rootNode:  #checking the rootnode #O(1)
            return
        else: 
            customQueue = queue.Queue()   #O(1)
            customQueue.enqueue(rootNode) #O(1)
            while not (customQueue.isEmpty()): #O(n)
                root = customQueue.dequeue() #O(1)
                print(root.value.data) 
                if (root.value.leftChild is not None): #O(1)
                    customQueue.enqueue(root.value.leftChild) 
                if (root.value.leftChild is not None): #O(1)
                    customQueue.enqueue(root.value.rightChild)


newBST = BSTNode(None) 
insertNode(newBST, 70)
insertNode(newBST, 60)
insertNode(newBST, 160)
insertNode(newBST, 30)
insertNode(newBST, 40)
insertNode(newBST, 100)
preOrderTraversal(newBST) 
inOrderTraversal(newBST)
postOrderTraversal(newBST) 
levelOrderTraversal(newBST)

print(newBST.leftChild.data)

Search in BST

In a BST, the right child is always bigger than the left child. So, when searching for a value, we compare it with the root node and then move to the left or right subtree. This speeds up our search.

Root node -> left subtree -> right subtree

(under the previous code) 
    def searchNode(rootNode, nodeValue): 
        if rootNode.data == nodeValue: #O(1)
            print("The value is founf") 
        elif nodeValue < rootNode.data: #O(1)
            if rootNode.leftChild.data == nodeValue: 
                print("The value is founf")
            else: #O(N/2)
                searchNode(rootNode.leftChild, nodeValue)
        else: 
            if rootNode.rightChild.data == nodeValue: #O(1)
                print("The value is founf")
            else: #O(N/2)
                searchNode(rootNode.rightChild, nodeValue)     
newBST = BSTNode(None) 
insertNode(newBST, 70)
insertNode(newBST, 60)
insertNode(newBST, 160)
insertNode(newBST, 30)
insertNode(newBST, 40)
insertNode(newBST, 100)     
searchNode(newBST, 60)

Time complexity: O(logN), Space complexity: O(logN)

Delete a node from BST

Here, we have three cases:

Case 1: The node to be delete is a leaf node

Case 2: The node has one child

Case 3: The node has two children

(under the previous code) 
    def minValueNode(bstNode): 
        current = bstNode
        while (current.leftChild is not None): 
            current = current.leftChild 
        return current

    def deleteNode(rootNode, nodeValue): 
        if rootNode is None: 
            return rootNode #O(1)
        if nodeValue < rootNode.data: #O(N/2)
            rootNode.leftChild = deleteNode(rootNode.leftChild, nodeValue)
        elif nodeValule > rootNode.data: #O(N/2)
            rootNode.rightChild = deleteNode(rootNode.rightChild, nodeValue)
        else: 
            if rootNode.leftChild is None: #O(1)
                temp = rootNode.rightChild
                rootNode = None 
                return temp 
            if rootNode.rightChild is None: #O(1)
                temp = rootNode.leftChild
                rootNode = None 
                return temp 
            temp = minValueNode(rootNode.rightChild) #O(logN)
            rootNode.data = temp.data #O(1)
            rootNode.rightChild = deleteNode(rootNode.rightChild, temp.data) #O(N/2)
        return rootNode

newBST = BSTNode(None) 
insertNode(newBST, 70)
insertNode(newBST, 60)
insertNode(newBST, 160)
insertNode(newBST, 30)
insertNode(newBST, 40)
insertNode(newBST, 100)  
deleteNode(newBST, 20)
levelOrderTraversal(newBST)

Time complexity: O(logN), Space complexity: O(logN)

Delete entire BST

(under the previous code) 
    def deleteBST(rootNode): 
        rootNode.data = None 
        rootNode.leftChild = None 
        rootNode.rightChild = None 
        return "The BST has been successfully deleted"

newBST = BSTNode(None) 
insertNode(newBST, 70)
insertNode(newBST, 60)
insertNode(newBST, 160)
insertNode(newBST, 30)
insertNode(newBST, 40)
insertNode(newBST, 100)  
deleteNode(newBST, 20)
print(deleteBST(newBST))
levelOrderTraversal(newBST)

Time complexity: O(1), Space complexity: O(1)

Time and space complexity of BST

	Time complexity	Space complexity
Create BST	O(1)	O(1)
Insert a node BST	O(logN)	O(logN)
Traverse BST	O(n)	O(n)
Search for a node BST	O(logN)	O(logN)
Delete node from BST	O(logN)	O(logN)
Delete entire BST	O(1)	O(1)

Basics of Binary Search Trees (BST)

Table of contents