CREATE OWN LIBRARY

Introduction:

A binary search tree is a binary tree data structure which has the following characteristics



(a) The left sub-tree of a particular node contains only nodes lesser than or equal to the node.

(b) The right sub-tree of a particular node contains only nodes greater than the node.

(c) The sub-trees are also binary search trees.

Insertion:

New nodes are inserted into the binary search tree using the following two rules  

(a) If the new node is lesser than or equal to the current node then the new node is inserted into the current node’s left sub-tree.

(b) If the new node is greater than the current node then the new node is inserted into the current node’s right sub-tree.

Traversal:

Binary search tree traversal is the process to visit every node of a binary search tree and display their values. There are three ways to traverse a binary search tree

●      In in-order traversal, the left sub-tree is visited first, then the root node followed by the right sub-tree. Every sub-tree is again considered to be a binary search tree.

●      In pre-ordertraversal, the root node is visited first, then the left sub-tree followed by the right sub-tree. Every sub-tree is again considered to be a binary search tree.

●      In post-ordertraversal, the left sub-tree is visited first, then the right sub-tree followed by the root node. Every sub-tree is again considered to be a binary search tree.

Search:

Whenever a node is to be searched in a binary search tree, the searching starts from the root node. If the value is lesser than the root, then the left sub-tree is searched, else the node is searched in the right sub-tree. This process is continued until the particular node has been found or no nodes are left in the tree.

Deletion

Whenever a node is to be deleted from a binary search tree, one of the three possibilities may arise

(a) The node to be deleted is a leaf node(i.e. it has no child nodes)

Just remove the node from the binary search tree. (b)The node to be deleted has only one child node

Copy the child node’s data into the node and then delete the child node from the binary search tree.

(c)The node to be deleted has two children nodes

Find the in-order successor of the node, copy the content’s of the in-order successor into the node and then remove the in-order successor from the binary search tree.

Algorithm:

Input: 

root which points to the root of the binary search tree.

Output:

(a) Binary search tree creation.

(b)Printing the binary search tree in in-order, post-order and pre-order.

(c)Searching a node in the binary search tree.

(d) Deleting a node from the binary search tree.

Algo:

Step 1: Start

Step 2:Defining the insert(temp,value) function

● If temp = NULL then,

(a) Set newNode[data]<=value.

(b) Return newNode.

● Else then,

(a)If value <=temp[data] then,

Set temp[left] <= insert(temp[left],value).

(b) Else then,

Set emp[right]<= insert(temp[right],value).

(c) Return temp.

Step 3: Defining the create() function

● Set root<= NULL.

● Set n<= number of elements

● Repeat for i =0 to n-1,

(a)Set value <= the value to be inserted.

(b)Set root <= insert(root,value).

●  Return root.

Step 4: Defining the preorder(temp) function

●  If temp != NULL then,

(a) Display temp[data]

(b) Call preorder(temp[left]).

(c) Call preorder(temp[right]).

Step 5: Defining the inorder(temp) function

●  If temp != NULL then,

(a)Call inorder(temp[left]).

(b)Display temp[data].

(c)Call inorder(temp[right]).

Step 6: Defining the postorder(temp) function

●  If temp != NULL then,

(a) Call postorder(temp[left]).

(b) Call postorder(temp[right]).

(c) Display temp[data].

Step 7: Defining the search(root,value) function

● Set temp <= root.

● Repeat substeps while temp !=NULL

(a) If temp[data] = value then,

Display “The value exists.”

Return.

(b) Else if value <temp[data] then,

Set temp <= temp[left]

(c) Else then,

Set temp <= temp[right]

●   Display “The value does not exist.”

Step 8: Defining the inorderSuccessor(temp) function

l Set t<= temp.

l  Repeat substeps while t!=NULL and temp[left]!=NULL(a) Set temp <= temp[left].

l  Return t.

Step 9: Defining the deleteNode(temp,value) function

● If temp = NULL then,

(a)Display “The value does not exist.”

(b) Return temp.

● If value<temp[data] then,

(a) Set temp[left]<= deleteNode(temp[left],value).

● Else if then,

(a)Set temp[right]<=deleteNode(temp[right],value).

● Else then,

(a) If temp[left] = NULL then,

Set t<= temp[right].

Return t.

(b)Else if temp[right] = NULL then,

Set t<= temp[left].

Return t.

(c) Set t<=inorderSuccessor(temp[right]).

(d) Set temp[data]<- t[data].

   (e)Set temp[right] deleteNode(temp[right],t[data])

● Return temp.

Step 10: