Binary Search Tree

To start with, lets understand what a tree datastructure is. A tree supports one way relation between objects of similar type. A very real example would be the way file system stores directories and files. A directory can have files as well as other directories which in turn can have more directories and files.

A Binary tree puts a restriction on tree that any node can have only 2 childs.

bst

A Binary search tree adds a property to binary tree that each node on left of parent node will have less key value than parent and each node on right will be higher key value. In turn, this also means at any point of time, for a node, whole left sub tree will have lower keys than the node value and right subtree will have higher values.

The above mentioned property helps in search operation. Lets say we are seaching for N

1. Go to root Node R.
2. Check if N is equal to R, return true.
3. if N>R, N=N.right (discard left tree)
4. if N