Binary Search Tree in Python

A binary tree is a type of data structure that resembles a tree. Each node of this tree contains two nodes called left and right. A Binary Search Tree is a special case of the more common binary tree data structure. The Binary Search Tree should follow the below-stated properties:

• The left subtree of any parent node of the tree should have a child node that has a value less than the parent node.
• The right subtree of any parent node of the tree should have a child node that has a value greater than the parent node.
• The left and right subtree of each node should also follow the above two properties of the Binary Search Tree.
• The Binary Search Tree does not contain any duplicate value.

These properties of the tree help maintain an ordering in the nodes so that the operations like searching, inserting, and finding minimum and maximum can be done in less time than it takes to execute these operations in an ordinary Binary Tree. Because then we need to compare the value of each node in order to get the values.

Searching a Value in the given Binary Tree?

Let us take an example of an array. If we have a normal array and we have to search for an element, we will be required to iterate through the elements of the array and compare each value. While if we have a sorted array, we can perform a binary search which is faster than the ordinary search operation. Likewise, in the case of the Binary Search Trees and the Binary Trees.

Now, let's say we need to search for an element in the binary search tree. Let the element be x.

• We will start the traversal from the root node of the given tree. First, we will compare the value of the root node with the value we want to search,
• If the two values are equal, then we are done with our search, and we will return the value. If the value we need to search is smaller than the value of the node, then that means we need to search in the left subtree of the node. If the value is larger, then we will go for the right subtree.

This is the main rule of the binary search tree. If the value is smaller, then we search in the left subtree. If the value is larger, then we search in the right subtree. The rule is analogous to the Binary Search in the array.

If the given binary tree is balanced (a balanced binary tree is the one for which the distance between the left and the right subtrees for all the nodes is not more than one), we will start by searching a space that contains n number of nodes. As we will discard the right or the left subtree after the first iteration, we will discard n/2 number of nodes. Similarly, in the next iteration, we will be left with only n/4 number of nodes. In this way, after each iteration, the search space is reduced by 2i, where i is the number of iterations.

Illustration of Searching in BST

Now we will see an example of the working of the Binary Search Tree:

Consider the following tree, and the value of x is 4.

Tree:

Steps

1. Initially, we will compare x with the value of the root node of the given tree, i.e., 9. Since 4 is less than 9, we will search for the value in the left subtree, hence, completely discarding the right subtree.
2. Now we will compare x with the current node value, which is 1. Since the value of x is greater than the value of the node, we will search for the value in the right subtree.
3. Next we will compare x with the next node value, i.e., 3. Since 4 is greater than 3, that means we will search in the right subtree.
4. The next node value is 4, which is equal to the x value. Hence the search is complete, and we have found the x value in the given Binary Search tree.

Below is the code implementing the search operation in Binary Search Tree.

Code

Output:

The node we are searching for is present in the given BST: 4

Time complexity: O(h) is the time complexity of this algorithm. Here h symbolizes the height of the given binary search tree. We are taking height here because we are performing DFS; therefore, in the worst-case scenario, we will traverse to the leaf node of the tree and thus take h.

Space complexity: The space complexity is O(h). Here h symbolizes the height of the given binary search tree. The space complexity is O(h) because the maximum space we need to store the recursion stack is equal to the number of nodes we are traversing, which is equal to the height of the tree.

Inserting the Given Value in BST?

The insertion operation in a binary search tree is similar to the search operation. There can be many ways to insert the node and also maintain the properties of the binary search tree. However, the easiest approach is to insert the node at the appropriate leaf node.

• We will start by comparing the value we want to insert with the value of the root node of the given BST.
• If the value we want to insert is less than the value of the root node, we will look for the leaf node in the left subtree.
• Otherwise, if the value is greater than the values of the root node, we will search in the right subtree.
• We will continue this process until we reach the leaf node.
• Now we will compare the value we want to insert to the value of the leaf node. If the value is smaller than the leaf node, we will create a left child of the leaf node.
• Otherwise, if the value is greater than the value of the leaf node, we will create the right child of the leaf node.

Illustrating Insert Operation in BST:

Let us see an example of the insertion operation in a BST

Consider the BST drawn below. In this tree, we have to add the value x = 5

Tree

Steps

1. We will start by comparing the root node value with x. Since x is less than 9, we will search for the leaf node in the left subtree
2. Now the value of the next node is 1. Since the value of x is greater than 1 therefore, now we will search for the right subtree
3. The next node value is 3. Since x is again greater than 3 therefore, we will search for the leaf node in the right subtree.
4. The next node value is 4, and it is a leaf node. Therefore, will insert 5 as a child of node 4. Since x is greater than 4, we will insert 5 as the right child of this node.

The final BST will look like this:

Tree

Below is the Python code for the implementation of the above algorithm of insertion operation.

Code

Output:

The tree before insertion:
0 1 3 4 9 10

The tree after insertion:
0 1 3 4 5 9 10

We can solve this problem using the iterative approach also. Below is the code to show how to insert a node in BST using the iterative function.

Code

Output:

The tree before insertion:
0 1 3 4 9 10

The tree after insertion:
0 1 3 4 5 9 10

Time Complexity: O(h) is the time complexity of the iterative approach. Here h symbolizes the height of the given BST. The time complexity is O(h) because we are following the Depth First Search instead of the Breadth First Search (or the inorder traversal).

Auxiliary Space: We have only created a new node to insert it into the tree. Since we have not used any variable, the space complexity of the iterative approach is O(1).