Home Data Structures Binary Search Tree Tutorial and Implementation

Binary Search Tree Tutorial and Implementation

Binary Search Tree(BST) is a type of tree data structure which has the following properties:

  1. It should be a Binary Tree i.e, each node should have at most 2 children.
  2. The keys in the left subtree are always less than or equal to the root(parent) node
  3. The keys in the right subtree are always greater than the root(parent) node.
  4. The left and right subtree should also be a binary tree.

Example of BST:

Binary Search Tree
Binary Search Tree

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:

  1. Preorder -> (Root, Left, Right)
  2. Inorder -> (Left, Root, Right)
  3. Postorder -> (Left, Right, Root)

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.

balanced and imbalanced binary search tree
balanced and imbalanced binary search tree

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
  1. Max, number of nodes in a binary search tree = 2^(+1)1, where h is the height of the BST
  2. Min number of nodes in a binary search tree = h, where h is the height of the BST
  3. Given n nodes, the total number of BST possible are 2n^Cn/(n+1)

Subscribe to our weekly newsletter

Join our community of 1000+ developers and stay updated with the fast moving world of computer science

We promise, we won't spam
Even we hate spam as much as you hate them

LEAVE A REPLY

Please enter your comment!
Please enter your name here