DEV Community

loading...
Cover image for Binary search tree in data structure

Binary search tree in data structure

Aya Bouchiha
Full stack web developer
Updated on ・2 min read

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.

Aya Bouchiha binary search tree in data structure

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

See you in the next post, on which we will cover the binary search tree implementation in detail, Happy Coding:)

#day_15

Discussion (0)