Posted

Reading Time: 1 minute

Binary Search Trees or BST is an ordered binary tree where all the nodes on the left of a node are less or equal to the node’s own value and all the values on the right are greater or equal to the node’s own value.

A Binary Tree is a tree with only two children, left and right.

Advantages of BST

  • lookup operation (locating a particular node in the tree) is fast and simple
    • Time: O(log(n)) for a balanced binary search tree
    • Worst case is O(n) where each node has only one child and it becomes a linked list
    • usually it happens
  • Insert/Delete are also O(log(n)) time in BSTs
  • you can obtain the smallest element by following all the left children and the largest element by following all the right children
  • Nodes can be printed in order in O(n) time
  • Given a node, you can even find the next highest node in O(log(n)) time.