Binary Search Tree (BST) definition and ADT

In a binary tree, every node can have a maximum of two children but there is no need to maintain the order of nodes basing on their values. In a binary tree, the elements are arranged in the order they arrive at the tree from top to bottom and left to right.

A binary tree has the following time complexities...

1.Search Operation - O(n)
2.Insertion Operation - O(1)
3.Deletion Operation - O(n)

To enhance the performance of binary tree, we use a special type of binary tree known as Binary Search Tree. Binary search tree mainly focuses on the search operation in a binary tree. Binary search tree can be defined as follows...

1. BST Definition: Binary Search Tree is a binary tree in which every node contains only smaller values in its left subtree and only larger values in its right subtree.

Binary Search Tree is a node-based binary tree data structure which has the following properties:

1. The left subtree of a node contains only nodes with keys lesser than the node’s key.
2. The right subtree of a node contains only nodes with keys greater than the node’s key.
3. The left and right subtree each must also be a binary search tree.
4. There must be no duplicate nodes.

AbstractDataType BSTree
{
  Instances:  Binary tree, each node has an element with a key field; all keys are distinct; keys in the left subtree of
                  any node are smaller than the key in the root node; those in the right subtree are larger.
  Operations:
   Create(): Creates an empty binary search tree.
   BuildTree(root,left,right): creates a binary search tree with root as the root element, left a left subtree, and right
                                          as right subtree.
   Preorder(visit): preorder travels of binary search tree.
   Inorder(visit): Inorder travels of binary search tree.
   postorder(visit): postorder travels of binary search tree.
   Levelorder(visit): level order travels of binary search tree.
   search(k,e): return in ‘e’ the element with ‘k’ return false if the operation fails, return tree if it succeeds.
}