Figure 1 shows a Binary Search Tree. This post will start with the motivation of studying BST and gradually move to the related definitions. We will do some hands on coding for simple BST operations and we will end the post by analysing the drawbacks.
Where do we use Binary Search Tree?
- Trees show relationships in the data
- Trees have efficient insertion and searching
- Trees are flexible. It allows moving subtrees with minimum effort
- Binary Search Tree or BST is a data structure which can be used to store the data in a sorted manner
- BST can act as a priority queue, i.e. can help in retrieving maximum and minimum fast
We will discuss some terminology related to Binary Search Tree here:
A binary tree is made of nodes. Each node contains a reference to “left” and “right” element. It also has a data element . Root is the top most node of a tree.
For any node A, except for the root node, we define parent node B as the node which connects A with a direct edge.
Each node can be connected to arbitrary number of nodes, also called as children. Nodes without children are called leaves or external nodes. Nodes other than external nodes are called internal nodes.
Any tree where all the nodes have at max two children is called Binary Tree. Figure 1 shows an example of Binary Tree.
Binary Search Tree
Binary Search Tree is a special case of Binary Tree where all the data element of nodes to the left of any parent node is less than the data element of the parent node. Also, the data element of nodes to the right of any parent node is greater than the data element of the parent node.
Figure 1 is an example of a BST.
Depth of a Node
Depth of a node is defined as number of edges from the root to the node. Node with data element 2 in figure 1 has depth of 1.
Height of Node
The height of a node is defined as the number of edges from the node to the deepest leaf. Node with data element 2 in figure 1 has height of 1. Height of tree is the height of the parent node.
Complete Binary Tree
A complete binary tree is a binary tree is defined as the tree in which each node has exactly zero or two children. Only possible exception can be bottom level, which is filled from left to right.
Figure 1 is an example of complete binary tree.
Quick test. Is the test shown in figure 4 a complete binary tree?
Codes For Insertion, Search and Transversal
Searching in a BST has O(tree height) worst-case runtime complexity. Binary search tree with n nodes has a minimum of O(log n) levels. It will take at least O(log n) comparisons to find a particular node. A binary search tree can be hugely unbalanced, making the search time to O(n).
Disadvantage of Binary Search Tree
- The shape of the tree depends on the order of insertions. At worst case, tree can be hugely unbalanced. That means, we might have to travel all the way down the height of tree to find a key
- Key of each visited node has to be compared with the key of the element to be inserted/found while inserting or searching. If key are long then the run time may increase.