Rajan Kumar

Rajan Kumar published an article

3 months, 1 week ago

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.

 


arrow_upward Upvote

comment Comment

arrow_downward downvote




Go back to feed

HackersFriend Updates


update Aug. 15, 2019, 1:47 p.m.

Full view page of article has been changed to match style of homepage feed. open_in_new


update Aug. 14, 2019, 12:52 a.m.

Total number posts on homepage is incresed to 10 by default and text-decoration of link to post and author is changed. open_in_new


update Aug. 7, 2019, 1:51 a.m.

We changed our homepage. Now, you can see newly published articles, directly on home page. open_in_new


View more


Events


event Nov. 28, 2018, 5:30 p.m.

Python from zero to hero

place Delhi

View details



event Aug. 13, 2018, 5:30 p.m.

Python from zero to hero

place Bangalore ( HackersFriend office BTM Layout)

View details