A binary search tree is a node-based binary tree data structure where each node has a comparable key (and associated value ) and satisfies the restriction that the key in any node is larger than the key in all nodes in that node’s left sub-tree and smaller than the key in all nodes in that node’s right sub-tree. Each non-leaf node has exactly two nodes. Each child must either a leaf node or the root of another binary tree. BST’s are also dynamic data structure and the size of a BST is only limited by the amount of free memory in the operating system.

The main advantages of binary search tree is that it remains ordered, which provide quicker search times than many other data structure.

**Properties of BST are following as :**

- One node is designed the root of the tree.
- Each internal node contains a key and has two sub-trees.
- Each sub-tree is itself a binary search tree.
- The leaves of the tree contain no key. Leaves are commonly represented by
*leaf*or*nil*symbol, a*Null pointer*etc. - The left sub-tree of a node contains only nodes with keys strictly less than node’s key.
- The right sub-tree of a node contains only nodes with keys strictly greater than the node’s key.

**Time Complexity of BST in big O notation :**

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