What is Binary search tree or sorted tree ?Write Algorithms for Binary Search Tree

Binary search tree:

  

This is another kind of tree data structure which is the variation of binary tree . A binary  search tree satisfy the following properties.

1. one of the element is called root.

2. the order elements are partition in to two subgroups left sub tree , right sub tree.

3.the elements of left sub tree must be less than the root.

4. the elements of right sub tree must be greater than the root.

5. Duplicate element does not exist.

6. every sub tree again a binary sub tree.

 (or)

A binary search tree is a collection of nodes where each node should contain at least two child nodes in such a way that left child is less than parent and right child is greater than parent and no duplicate node exist.

o/p : 8 14 18 20 23 38 45 50 70 82 98

note : If the binary search tree is traversing in Inorder then we get the ascending order of the list.

Algorithm for Binary Search Tree :

                   

Insertion algorithm :

 A new node is inderted in to a binary search tree as follows.

If the root node is null then tha new node is made as the root node. If the data in the root node is greater than the key value then insertion is performed in its left subtree . If the data in the root node is less than the key value then insertion is performed at right node. If the data in the root node is equal to key value then insertion is not possible. Because the binary search tree does not contain duplicate elements . The following is the recursive algorithm to insert a node in to the binary search tree.

Insertion(BinarySearchTree p, int key)

Begin

if( p== null) then

p--> new binary search tree in code( )

p.data --> key

p. left --> null

else if (p. data > key) then

insertion (p. left . key)

else if(p. data

insertion(p. right .key)

else print duplicate value

end if

end

Binary Search Algorithm:

The algorithm is to search whether the given key value exists or not in a binary search tree. The key value is compared with data in the root node. If it is equal then searching is completed.

If the key value is greater than the data in the root node then searching is performed in its right sub tree.

If the key value is less than the data in the root node then searching is performed in its left subtree. This process is repeated until key value is found or no more elements to search.

binarySearch ( BinarySearchTree node, int key)

Initialize found ¬ 0

while(p! =null)

do

if(p. data == key) then

found --> 1

break

else if( p. data ->key ) then

p--> p.right

p--> p.left

else

end if

alone

if(found ==1) then

display key is not found

end if

end