Binary Search Tree(BST) is a type of tree data structure which has the following properties:

- It should be a Binary Tree i.e, each node should have at most 2 children.
- The keys in the left subtree are always less than or equal to the root(parent) node
- The keys in the right subtree are always greater than the root(parent) node.
- The left and right subtree should also be a binary tree.

Example of BST:

This is a BST, as all nodes less than root node 8 are on the left, and all nodes greater than the root node 8 are on the left.

Also, all the subtrees also follow the BST property.

The height of this tree is 3.

##### Time Complexity for Various operation in BST

## Algorithm / Operation |
## Average Case |
## Worst Case |

Height | O(log N) | O(N) |

Search | O(log N) | O(N) |

Insert | O(log N) | O(N) |

Delete | O(log N) | O(N) |

Tree Traversal | O(N) | O(N) |

##### Tree Traversal

We have 3 algorithms for Tree Traversal:

The time complexity of Tree traversal is O(N), where N is the number of nodes in the tree, because no matter which traversal method we use, we have to go and visit each element of a tree at least once, hence if there are N nodes then work done = asymptotic time to visit each node = O(N)

##### Best and Worst Case Height of BST

The BST has best-case height O(log N) when it is perfectly balanced, i.e, the height of the left subtree and right subtree is equal.

The BST has worst-case height O(N) if the tree is left or right-skewed.

The left tree above is completely balanced and has height = 2(*O(logN), N= 6 = no. of nodes in the tree*)

The tree on right has height = 5 ( O(N-1) or O(N), here N = 6= no. of nodes in the tree)

##### Other important properties

- Max, number of nodes in a binary search tree = 2^(ℎ+1)−1, where h is the height of the BST
- Min number of nodes in a binary search tree = h, where h is the height of the BST
- Given n nodes, the total number of BST possible are 2n^Cn/(n+1)