Binary Search Tree (BST) with Example

In this Data Structure tutorial, you will learn:

• What is a Binary Search Tree?
• Attributes of Binary Search Tree
• Why do we need a Binary Search Tree?
• Types of Binary Trees
• How Binary Search Tree Works?
• Important Terms

Attributes of Binary Search Tree

A BST is made of multiple nodes and consists of the following attributes:

• Nodes of the tree are represented in a parent-child relationship
• Each parent node can have zero child nodes or a maximum of two subnodes or subtrees on the left and right sides.
• Every sub-tree, also known as a binary search tree, has sub-branches on the right and left of themselves.
• All the nodes are linked with key-value pairs.
• The keys of the nodes present on the left subtree are smaller than the keys of their parent node
• Similarly, The left subtree nodes' keys have lesser values than their parent node's keys.

1. There is the main node or parent level 11. Under it, there are left and right nodes/branches with their own key values
2. The right sub-tree has key values greater than the parent node
3. The left sub-tree has values than the parent node

Why do we need a Binary Search Tree?

• The two major factors that make binary search tree an optimum solution to any real-world problems are Speed and Accuracy.
• Due to the fact that the binary search is in a branch-like format with parent-child relations, the algorithm knows in which location of the tree the elements need to be searched. This decreases the number of key-value comparisons the program has to make to locate the desired element.
• Additionally, in case the element to be searched greater or less than the parent node, the node knows which tree side to search for. The reason is, the left sub-tree is always lesser than the parent node, and the right sub-tree has values always equal to or greater than the parent node.
• BST is commonly utilized to implement complex searches, robust game logics, auto-complete activities, and graphics.
• The algorithm efficiently supports operations like search, insert, and delete.

Types of Binary Trees

Three kinds of binary trees are:

• Complete binary tree: All the levels in the trees are full of last level's possible exceptions. Similarly, all the nodes are full, directing the far left.
• Full binary tree: All the nodes have 2 child nodes except the leaf.
• Balanced or Perfect binary tree: In the tree, all the nodes have two children. Besides, there is the same level of each subnode.

How Binary Search Tree Works?

The tree always has a root node and further child nodes, whether on the left or right. The algorithm performs all the operations by comparing values with the root and its further child nodes in the left or right sub-tree accordingly.

Depends upon the element to be inserted, search, or deleted, after the comparison, the algorithm can easily drop the left or right subtree of the root node.

BST primarily offers the following three types of operations for your usage:

• Search: searches the element from the binary tree
• Insert: adds an element to the binary tree
• Delete: delete the element from a binary tree

Each operation has its own structure and method of execution/analysis, but the most complex of all is the Delete operation.

Search Operation

Always initiate analyzing tree at the root node and then move further to either the right or left subtree of the root node depending upon the element to be located is either less or greater than the root.

1. The element to be searched is 10
2. Compare the element with the root node 12, 10 < 12, hence you move to the left subtree. No need to analyze the right-subtree
3. Now compare 10 with node 7, 10 > 7, so move to the right-subtree
4. Then compare 10 with the next node, which is 9, 10 > 9, look in the right subtree child
5. 10 matches with the value in the node, 10 = 10, return the value to the user.

Insert Operation

This is a very straight forward operation. First, the root node is inserted, then the next value is compared with the root node. If the value is greater than root, it is added to the right subtree, and if it is lesser than the root, it is added to the left subtree.

1. There is a list of 6 elements that need to be inserted in a BST in order from left to right
2. Insert 12 as the root node and compare next values 7 and 9 for inserting accordingly into the right and left subtree
3. Compare the remaining values 19, 5, and 10 with the root node 12 and place them accordingly. 19 > 12 place it as the right child of 12, 5 < 12 & 5 < 7, hence place it as left child of 7.
   1. Now compare 10, 10 is < 12 & 10 is > 7 & 10 is > 9, place 10 as right subtree of 9.

Delete Operations

Delete is the most advanced and complex among all other operations. There are multiple cases handled for deletion in the BST.

• Case 1- Node with zero children: this is the easiest situation, you just need to delete the node which has no further children on the right or left.
• Case 2 - Node with one child: once you delete the node, simply connect its child node with the parent node of the deleted value.
• Case 3 Node with two children: this is the most difficult situation, and it works on the following two rules
  • 3a - In Order Predecessor: you need to delete the node with two children and replace it with the largest value on the left-subtree of the deleted node
  • 3b - In Order Successor: you need to delete the node with two children and replace it with the largest value on the right-subtree of the deleted node

1. This is the first case of deletion in which you delete a node that has no children. As you can see in the diagram that 19, 10 and 5 have no children. But we will delete 19.
2. Delete the value 19 and remove the link from the node.
3. View the new structure of the BST without 19

1. This is the second case of deletion in which you delete a node that has 1 child, as you can see in the diagram that 9 has one child.
2. Delete the node 9 and replace it with its child 10 and add a link from 7 to 10
3. View the new structure of the BST without 9

1. Here you will be deleting the node 12 that has two children
2. The deletion of the node will occur based upon the in order predecessor rule, which means that the largest element on the left subtree of 12 will replace it.
3. Delete the node 12 and replace it with 10 as it is the largest value on the left subtree
4. View the new structure of the BST after deleting 12

1. 1 Delete a node 12 that has two children
2. 2 The deletion of the node will occur based upon the In Order Successor rule, which means that the largest element on the right subtree of 12 will replace it
3. 3 Delete the node 12 and replace it with 19 as it is the largest value on the right subtree
4. 4 View the new structure of the BST after deleting 12

Important Terms

• Insert − Inserts an element in a tree/create a tree.
• Search − Searches an element in a tree.
• Preorder Traversal − Traverses a tree in a pre-order manner.
• Inorder Traversal − Traverses a tree in an in-order manner.
• Postorder Traversal − Traverses a tree in a post-order manner.

Summary

• BST is an advanced level algorithm that performs various operations based on the comparison of node values with the root node.
• Any of the points in a parent-child hierarchy represents the node. At least one parent or root node remains present all the time.
• There are a left subtree and right subtree. The left subtree contains values that are less than the root node. However, the right subtree contains a value that is greater than the root node.
• Each node can have either zero, one, or two children.
• A binary search tree facilitates primary operations like search, insert, and delete.
• Delete being the most complex have multiple cases, for instance, a node with no child, node with one child, and node with two children.
• The algorithm is utilized in real-world solutions like games, autocomplete data, and graphics.