What is Binary search tree or sorted tree ?Write Algorithms for Binary Search Tree
![](http://img2.blogblog.com/img/icon18_edit_allbkg.gif)
https://www.computersprofessor.com/2016/11/what-is-binary-search-tree-or-sorted.html
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