C++ program to convert Sorted Array to binary search tree














































C++ program to convert Sorted Array to binary search tree



#include<iostream>
#define teste {cout<<"HELLO";exit(0);}
using namespace std;
//Class for Node which has three members
class Node
{
	public: 
		int value;
		Node *leftChild,*rightChild;
		Node()
		{
			value=0;
			leftChild=NULL;
			rightChild=NULL;
		}
};

//Function for inorder traversal of binary serach tree
void inOrderDisplay(Node* t)
{
	if(t!=NULL)
	{
		inOrderDisplay(t->leftChild);
		cout<<t->value<<" ";
		inOrderDisplay(t->rightChild);
	}
}

//Function for converting a sorted array to BST
//Arguments:	array 'a[]', 'start' indicating start index of array,
//				'end' indidcating end index of array
//Returns:		A pointer to Node class object
Node* sortedArraytoBST(int a[],int start,int end)
{
	//Base case
	if(start>end)
	{
		return NULL;
	}

	//Get middle element and store in newNode's value member
	int mid=(start+end)/2;
	Node* newNode=new Node();
	newNode->value=a[mid];

	//Recursively call the function for left hafl and right half of input array
	newNode->leftChild=sortedArraytoBST(a,start,mid-1);
	newNode->rightChild=sortedArraytoBST(a,mid+1,end);

	//Finally return the the pointer to newNode
	return newNode;

}

int main()
{
	//Declare the necessary variables
	int *arr,n;

	//Get the size of the array from user
	cout<<"\nEnter the size of the array:";
	cin>>n;

	//Dynamically allocate memory for the array
	arr=new int[n];

	//Get the array input from the user
	cout<<"\nEnter the elements of the array:";
	for(int i=0;i<n;i++)
	{
		cin>>arr[i];
	}

	//Create a root node and assign the return value of the function call 
	//to it
	Node* t=sortedArraytoBST(arr,0,n-1);

	//Finally, display the tree, done by inorder traversal
	cout<<"\nBST traversed inorder:";
	inOrderDisplay(t);
	cout<<endl;

	return 0;
}

More Articles of Siddeshwar Navaneetharan:

Name Views Likes
C++ program to convert Sorted Array to binary search tree 144 1

Comments