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.

https://upload.wikimedia.org/wikipedia/commons/thumb/d/da/Binary_search_tree.svg/300px-Binary_search_tree.svg.png

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).

Example:

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

 

 

Time Complexity

Space Complexity

 

Average

Worst

Worst

Data Structure 

 Access 
 Search 
 Insertion 
 Deletion 
 Access 
 Search 
 Insertion 
 Deletion 
 

Binary Search Tree

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