Binary Search Tree(BST) is a type of tree data structure which has the following properties:
- It should be a Binary Tree i.e, each node should have at most 2 children.
- The keys in the left subtree are always less than or equal to the root(parent) node
- The keys in the right subtree are always greater than the root(parent) node.
- The left and right subtree should also be a binary tree.
Example of BST:
This is a BST, as all nodes less than root node 8 are on the left, and all nodes greater than the root node 8 are on the left.
Also, all the subtrees also follow the BST property.
The height of this tree is 3.
Time Complexity for Various operation in BST
Algorithm / Operation |
Average Case |
Worst Case |
| Height | O(log N) | O(N) |
| Search | O(log N) | O(N) |
| Insert | O(log N) | O(N) |
| Delete | O(log N) | O(N) |
| Tree Traversal | O(N) | O(N) |
Tree Traversal
We have 3 algorithms for Tree Traversal:
The time complexity of Tree traversal is O(N), where N is the number of nodes in the tree, because no matter which traversal method we use, we have to go and visit each element of a tree at least once, hence if there are N nodes then work done = asymptotic time to visit each node = O(N)
Best and Worst Case Height of BST
The BST has best-case height O(log N) when it is perfectly balanced, i.e, the height of the left subtree and right subtree is equal.
The BST has worst-case height O(N) if the tree is left or right-skewed.
The left tree above is completely balanced and has height = 2(O(logN), N= 6 = no. of nodes in the tree)
The tree on right has height = 5 ( O(N-1) or O(N), here N = 6= no. of nodes in the tree)
Other important properties
- Max, number of nodes in a binary search tree = 2^(ℎ+1)−1, where h is the height of the BST
- Min number of nodes in a binary search tree = h, where h is the height of the BST
- Given n nodes, the total number of BST possible are 2n^Cn/(n+1)