Rajan Kumar

rajan

Founder & Programmer at HackersFriend Updated Aug. 14, 2019, 4:24 p.m. ⋅ 72 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.

 



arrow_upward Upvote

comment Comment

arrow_downward downvote



Go back to feed

HackersFriend Updates





View more


Events


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

Python from zero to hero

place Delhi

View details


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

Python from zero to hero

place Bangalore ( HackersFriend office BTM Layout)

View details