Introduction To Binary Search Tree

What is Binary Search Tree?

A tree data structure can have any number of branches from every node but in binary tree each node only has two branches. And binary search tree is binary tree that is ordered. That means each left sub-tree is less than or equal to the parent node and each right sub-tree is greater than or equal to the parent node. In fact the picture above is a example to binary search tree.

Why Use Binary Search Tree?

Because the use the principle of binary search, on average the operations are able to skips about half of the tree. So, for each for search, insertion and deletion takes time proportional to the logarithm of number of items stored in the tree. For example, if we are looking for a small value, we only have to search through the left nodes and ignore the right children.

When to Use Binary Search Tree?

Binary search tree is useful in case where elements can be compared to less than or greater than manner. For example- if we have bunch of names saved and we want to search a particular name.

Time complexity

  • Insertion: O(log n)
  • Deletion: O(log n)
  • Search: O(log n)

--

--

Software Engineer

Love podcasts or audiobooks? Learn on the go with our new app.

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store