Binary Search Tree is a node-based binary tree data structure which has the following properties:
- The left subtree of a node contains only nodes with keys lesser than the node%u2019s key.
- The right subtree of a node contains only nodes with keys greater than the node%u2019s key.
- The left and right subtree each must also be a binary search tree.
Algorithm
The mid-value of the given sorted array would represent the root of one possible BST that can be constructed from the given array elements.
1. Find the middle element of the array and make it root(Now the array is divided into two halves left and right, where the left half is our left subtree and right half, is our right subtree)
2. Recursively do the same for the left half and right half.
(a) Get the middle of left half and make it left child of the root created into Step 1.
(b) Get the middle of right half and make it right child of the root created into Step 1.
3. The base condition that would terminate the recursion would then be if low boundary index exceeds high boundary index, in which case return null.
using namespace std;
struct Node
{
int data;
Node *left; //pointer points to left node
Node *right; //pointer points to right node
};
/*function that returns new node*/
Node *newNode(int x)
{
Node *temp = new Node(); //temp points to the dyanamically formed node
temp->data = x;
temp->left = NULL;
temp->right = NULL;
return temp; //return the address of the node temp is pointing
}
Node *arrayToBST(int *arr, int start, int end)
{ /* Base Case*/
if(start > end)
{
return NULL;
}
/*Get the middle element and make it root*/
int mid = (start + end)/2;
Node *root = newNode(arr[mid]);
/* Recursively construct the left subtree
and make it left child of root */
root->left = arrayToBST(arr,start,mid-1);
/* Recursively construct the right subtree
and make it right child of root */
root->right = arrayToBST(arr,mid+1,end);
return root;
}
/*Function inOrder prints inorder traversal of the tree
inorder traversal prints element in sorted order
*/
void inOrder(Node *node)
{ if(node == NULL)
return;
inOrder(node->left);
cout<<node->data<<" ";
inOrder(node->right);
}
int main()
{ int arr[] = {2, 4, 5, 6, 7, 10, 11, 15};
/*Number of elements in the array (total size of the array / size of one element )
In this case elements are integer */
int n = sizeof(arr)/sizeof(arr[0]);
Node *root = arrayToBST(arr,0,n-1);
inOrder(root);
return 0;
}
OUTPUT:
2 4 5 6 7 10 11 15
Our inorder traversal prints elements in sorted order, so our binary search tree is correct.
Time Complexity
T(n) = 2T(n/2) + C
By Master Theorem
T(n) = O(n)
