FOR FREE YEAR SOLVED

Tree Search is a searching technique that is totally dependent on the data structure of a binary search tree. In this searching technique first, the binary search tree is created from the given data. A binary search tree is a special type of binary tree in which, for each parent node, the left child will be lesser or smaller than the parent node and the right child will be equal or greater than the parent node. After creating the binary search tree, the element is taken from the user and then first compared with the element at the root. If the element is matched then “Element found” is printed. If not, then it is checked whether the searched element is lesser than or greater than the root element. If it is lesser than the root element then the left sub-tree is searched in the same way, and if the element is greater than the root element then the right sub-tree is searched.

EXAMPLE:

Suppose there is 6 elements as follows:

Now the binary search tree will be created as follows. The first element will be inserted as the root node. The tree will be:

The 2nd element is 32 which is greater than 9, so it will be inserted as the right child of the root node 9. The tree will be:

The next element is 5, so it will be first compared with 9, as it is lesser than 9 so it will be inserted as the left child of the tree. Hence, the new tree will be:

The next element is -2. First, it will be compared with 9. As it is lesser than 9, it will move to the left sub-tree, then it will be compared with the left child of 9, i.e. 5. As -2 is lesser than 5 also, then it will be inserted as the left child of 5. The tree will be:

The next element is 7 which is to be inserted into the binary search tree. Again the same process of insertion will be performed. As 7 is lesser than 9, it will be inserted in the left sub-tree, now 7 is greater than 5 so it will be inserted as the right child of 5 and the tree will be:

The last element is 23 that is to be inserted into the tree. It will be compared with the root element 9, as it is greater than 9, which means it would be inserted into the right sub-tree. Now it will be compared with 32, as 23 is lesser than 32, so it will be inserted as the left child of 32. So the final tree will be:

Now let the searched element be 7.

First the pointer ‘ptr’ will be pointing to the root element.

So, the element will be compared with the root element i.e. 9. As they are not matched, it will be checked whether the element is greater than or lesser than the root element. In this case, 7 is lesser than 9, then the left sub-tree will be searched. Pointer ‘ptr’ will be pointing to the left child of the root.

The next element of the left sub-tree is 5 which is also a root. Now 7 will be compared with 5. They are not equal, but 7 is greater than 5. So, the right sub-tree will be checked. The pointer ‘ptr’ will be moved to the right child of 5.

The right child of 5 is 7 which is equal to the searched element, so “element found” will be printed.

INPUT: The elements of the tree, and element to search
OUTPUT: whether the element is present in the tree or not
PROCESS:
Step 1: [Take the inputs from the user]
Read n
For i=0 to n repeat
Read arr[i]
	   [End of ‘for’ loop]
Step 2: [Create the Binary Search Tree with the elements]
Create a node of tree structure with the data to be inserted pointed by a node type pointer ‘p’
Set data[p]<-x
		Set left[p]<-NULL
Set right[p]<-NULL
		Set str<-root
Set ptr<-root
		while(ptr≠NULL) repeat
			Set str<-ptr
			if x<data[ptr] then
				Set ptr<-left[ptr]
			else
				Set ptr<-right[ptr]
		[End of ‘while’ loop]
		if  x<data[str] then
			Set left[str]<-p
		else
			Set right[str]<-p
[End of function to create the search tree]
Step 3: [Inorder traversal of tree]
if  root≠NULL then
  		Call inorder(left[root]) i.e. For the left sub tree
  		Print data[root]
  		Call inorder(right[root]) i.e. For the right sub tree
[End of the function ‘inorder’]
Step 4: [Search function to search the element]
	Set f<-0
 	Set ptr<-root
 	While ptr≠NULL repeat
		If x=data[ptr] then
			Print "The element found"
			Set f<-1	
		[End of ‘if’]
		If x<data[ptr] then
			Set ptr<-left[ptr]
		else
			Set ptr<-right[ptr]
		[End of ‘if’]
	[End of ‘while’ loop]
	If f=0 then
		Print "Element not found"
	[End of ‘if’]
Step 5: [Creating the tree]
	Read x
Create the root node with the first element of the array by setting data[root]<-x
 	Set left[root]<-NULL
Set right[root]<-NULL
 	For i=1 to n-1 repeat
		Read x
 		Call insert_node(x) function to insert the element into the search tree
 	Print the sorted array by calling ‘inorder(root)’ function
	Read x
	Call the function ‘search(x)’ to search the element x in the tree whether it is present or not
Step 6: Stop.