Tutorials  Articles  Notifications  Login  Signup


RK

Rajan Kumar

Founder at HackersFriend Updated Aug. 14, 2019, 4:24 p.m. ⋅ 1471 views

What is Binary Search Tree (BST) ?


Binary Search Tree or BST, is a Binary tree based data sctructure, that keeps all of its elements in sorted order. We also call it, ordered or sorted binary trees.

It was invented by P.F. Windley, A.D. Booth, A.J.T. Colin, and T.N. Hibbard in 1960. 

    

Binary Search Tree

Specifications

  • Faster lookup for elements
  • Faster insertion of new elements
  • and faster removal of elements from tree
  • Left subtree of a node contains only nodes with keys lesser than the node’s key.
  • Right subtree of a node contains only nodes with keys greater than the node’s key.
  • Left and right subtree each must also be a binary search tree.

So, overall, BST is a container that keeps elements inside it and provides access to it in efficient manner.

 

Complexity

Operation Average Case Worst case
Space O(n) O(n)
Search O(log n) O(n)
Insert O(log n) O(n)
Delete O(log n) O(n)

 

 

 How does it work ?

BST keeps all of its elemets in sorted order hence operations like, search, insert and delete works based Binary search and this gives it advantage.

 



HackerFriend Logo

Join the community of 1 Lakh+ Developers

Create a free account and get access to tutorials, jobs, hackathons, developer events and neatly written articles.


Create a free account