A binary tree where the left child contains only nodes with values less than the parent node, and where the right child only contains nodes with values greater than or equal to the parent node, is called Binary search tree.

bsearch1
There are three types of traversal explained here with example code:

  • In order traversal
  • Pre order traversal
  • Post order traversal

 

 

 

Time complexity:

Average 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)

Ref: Wikipedia.org