BST (Binary Search Tree) is ordered Binary Tree.

In Binary Search Tree is a Binary Tree with following additional properties:

  1. The left subtree of a node contains only nodes with keys less than the node’s key.
  2. The right subtree of a node contains only nodes with keys greater than the node’s key.
  3. The left and right subtree each must also be a binary search tree.

Each of whose vertices is assigned a key, such that the key assigned to any vertex v is greater than the key at each vertex of the left subtree at v and less than the key at any vertex of the right subtree of v.

Time Complexities:

  • Search:  O(h)
  • Insertion: O(h)
  • Deletion: O(h)
  • Extra Space: O(n) for pointers
  • h: Height of BST
  • n: Number of nodes in BST

If Binary Search Tree is Height Balanced, then h = O(Log n) 

Self-Balancing BSTs such as AVL Tree, Red-Black Tree, and Splay Tree make sure that height of BST remains O(Log n).

BST provide moderate access/search (quicker than Linked List and slower than arrays).
BST provide moderate insertion/deletion (quicker than Arrays and slower than Linked Lists).


  • Product sorting in e-commerce site
  • Groping or sorting video files on Youtube, Netflix



Time Complexity

Space Complexity





Data Structure 


Binary Search Tree

Θ(log(n)) Θ(log(n)) Θ(log(n)) Θ(log(n)) O(n) O(n) O(n) O(n) O(n)