Summary This is very useful study material

Binary Search Tree(BST)
Binary search tree is a data structure that quickly allows us to maintain a sorted list of
numbers.
It is called a binary tree because each tree node has a maximum of two
children.
It is called a search tree because it can be used to search for the presence of a number
in O(log(n)) time.
The1.properties that separate a binary search tree from a regular binary tree is
All nodes of left subtree are less than the root node
2. All nodes of right subtree are more than the root node
3. Both subtrees of each node are also BSTs i.e. they have the above two properties

, 8 8


10 3 10


1 6 1)

2



X
A tree having a right subtree with one value smaller than the root is shown to demonstrate
that it is not a valid binary search tree
The binary tree on the right isn't a binary search tree because the right subtree of the node "3"
containsa value smaller than it.
There are two basic operations that you can perform on a binary search tree:
Search Operation
The algorithm depends on the property of BST that if each left subtree has values below root
and each right subtree has values above the root.
If the value is below the root, we can say for sure that the value is not in the right subtree; we
need to only search in the left subtree and if the value is above the root, we can say for sure
that the value is not in the left subtree; we need to only search in the right subtree.
Algorithm:
If root == NULL
return NULL;
If number == root->data
return root->data;
If number < root->data
return search(root->left)
If number > root->data
return search(root->right)
Let us try to visualize this with a diagram.