Hi, in this is part 3 of the tree data structure, we're going to discuss the Binary search tree, and in the next post, we will cover in detail its implementation (insertion, searching, and deletion).
Binary search tree (BST)
- Binary search tree: or (sorted binary tree) is a binary tree invented in (1960) which all nodes that exist in the right sub-tree are greater than the nodes that exist in the left sub-tree and there parent node. and Both the left and right subtrees must be binary search trees as well.
Space complexity of binary search tree
- The space complexity of the binary search tree is O(n) where n is the number of elements.
Time complexity of binary search tree
| insert | search | delete | |
|---|---|---|---|
| best case | O(log n) | O(log n) | O(log n) |
| worst case | O(n) | O(n) | O(n) |
The time complexity of the Binary search tree becomes O(n) if the binary tree is a skewed binary tree.
Advantages of using a binary search tree
- Faster than array and Linked list in insertion and deletion.
- It is so Efficient in searching
- getting The minimum and the Maximum easily
Disadvantages of using a binary search tree
- More stack space due to the recursion
- The run time mat increases because of the comparisons.
References and useful resources
- https://www.geeksforgeeks.org/binary-search-tree-set-1-search-and-insertion/
- https://afteracademy.com/blog/binary-search-tree-introduc tion-operations-and-applications
- https://www.quora.com/What-are-some-practical-applications-of-binary-search-trees
- https://www.upgrad.com/blog/binary-tree-in-data-structure/
- https://www.coursehero.com/file/p1fldsp9/Disadvantages-of-Binary-Search-Trees-The-shape-of-the-tree-depends-on-the-order/
- https://www.javatpoint.com/binary-search-tree
See you in the next post, on which we will cover the binary search tree implementation in detail, Happy Coding:)
#day_15
Top comments (0)