Construct BST from given preorder traversal

Let's start by understanding the problem statement of constructing Binary Search Tree (or BST) from given preorder traversal.

You are given a preorder array traversal, using a preorder array traversal you have to construct a BST.

Hint:

A Binary Search Tree is a tree where every node has its left child node data value smaller than the data value of itself and every right child of the parent node in BST is greater than it’s value, so accordingly the programmer has to keep track of the elements that are inserted.

Quick Think:

For creating a Binary Search Tree using a preorder array traversal, we need to ponder over the following points:

• The index of the array element should not be greater than the total size of the preorder array, as if it becomes greater than NULL is to be returned.

• The second condition to be checked is that the key value or the value which is to be inserted to the BST must be greater than the minimum number in the range and less than the maximum number in the range because BST is all about the data values in the range and the left child node data values are less than the parent node and right child node data values is greater in data value than the parent node.

• Now the next condition to be checked is that the index of the next data node value to be inserted is less than the total size of the preorder array traversal.

• As explained before the left child node has a data value less than the parent node and the right child node has a data value greater than the parent node, so for construction of the left child node the key value should lie between the minimum number and the last key value of the data node pushed into the BST.

Algorithm:

A function is defined for the execution of the following problem with arguments as the preorder traversal array, index of the current array element to be pushed into the BST, a variable to keep track of the minimum element in the preorder traversal array, a variable to keep track of the maximum element in the preorder traversal array and the size of the preorder traversal array.

Step 1: After the creation of the function we will check our first condition as mentioned above that whether the index of the array element is smaller than or equal to the size of the preorder traversal array if this condition is ‘True’ then go to step 2 else return NULL.

Step 2: Now for the second step we will go for the condition that the key element or the element to be inserted next is greater than the minimum number in the range and less than the maximum number in the range if this condition is ‘True’ then go to step 3 else go to step 7.

Step 3: Now a temporary node is declared to store the newly created node, and the index is incremented by 1 for the next element in the preorder traversal array to be the part of the BST.

Step 4: Now the other condition is checked which is about the index of the current increment index in the array if it is less than the size of the preorder traversal array then go to step 5 else check for the next element.

Step 5: Now for the left child node of the present node we must have the next array element be greater than the minimum element in the range and smaller than the maximum element in the range so after the formation of the parent node in step 3, we will have the left child should be smaller than the current parent node formed and greater than the minimum number in the range and hence a recursive call is made for the same function with the above-given arguments with the max number to be the data of the parent node formed in step 3.

Step 6: And for the right child node we have the right child should be greater than the current parent node formed in step 3 and smaller than the maximum number in the range and hence a recursive call is made for the same function with the above-given arguments with the min number to be the data of the parent node created in step 3.

Step 7: Return the created node.

Implementation of the above Algorithm:

Now let's see the implementation of the above algorithm.

#include <bits/stdc++.h>
using namespace std;
struct node
{
	int data;
	struct node *left, *right;
};

/*Function to return the newly created node of the tree. */
struct node* newnode(int data)
{
	struct node * node;
	node = (struct node *) malloc(sizeof(struct node));
	node->data = data;
	node->left = NULL;
	node->right = NULL;
	return node;
}

struct node* create_BST(int pre[], int *index, int min, int max, int key, int n)
{
	/*Base condition for termination of the recursive function. */
	if (*index >= n)
		return NULL;
	struct node *temp = NULL;
	/*Condition to check for the condition of BST. */
	if (key > min && key < max)
	{
		temp = newnode(key);
		*index = *index + 1;
		if (*index < n)
		{ /*Left child has data value less than the parent node. */
			temp->left = create_BST(pre, index, min, key, pre[*index], n);
			/*Right child has data value more than the parent node. */
			temp->right = create_BST(pre, index, key, max, pre[*index], n);
		}
	}

	return temp;
}

/*Function to print the inorder traversal of tree using a stack. */
void traversal(struct node *root)
{
	if (root == NULL)
		return;
	stack<node*> s;
	struct node *temp = root;
	while (!s.empty() || temp != NULL)
	{
		while (temp != NULL)
		{
			s.push(temp);
			temp = temp->left;
		}

		temp = s.top();
		s.pop();
		cout << temp->data << " ";
		temp = temp->right;
	}
}

/*Driver function to check the above algorithm. */
int main()
{
	int pre[] = { 10, 5, 1, 7, 40, 50 };

	int size = sizeof(pre) / sizeof(pre[0]);
	int index = 0;

	struct node *root = create_BST(pre, &index, INT_MIN, INT_MAX, pre[0], size);

	printf("Inorder traversal of the constructed tree: \n");
	traversal(root);

	return 0;

}

Running time complexity of the above algorithm is O(n^2).
The output of the above algorithm is: 1 5 7 10 40 50.

Explanation of the above Code:

Let us consider an array as given in the code above, i.e., pre[ ] = {10, 5, 1, 7, 40, 50}. Now we will create a recursive function that will accept the following arguments which are the preorder array, the index of the current element, the minimum integer in the range, the maximum number in the range, the current element from the preorder array traversal, and the total size of the array as shown in the above diagram. Follow the steps below to get through our final output.

1. The function is called with the above-written arguments, now our first condition will be to check for the present index of the array element, here we have the index of the current element less than the total size of the array.

   

2. Now we move to the next condition which says that the current array element must be greater than the minimum number in the range and smaller than the maximum number in the range, in this case, this is ‘True’ so we move to our next now, we will define a temporary node to store the node created from the current element from the array and increment the current index by one as shown in the above diagram.

   

3. Now we move on to our next condition to check whether the current increment index is less than the total size of the array, in this case, which is ‘True’ so, we will form the left child node of the current parent node which is done by making a recursive call to the defined function above with arguments as preorder array traversal, index to the next element in the array, minimum number in the range, the maximum number in the range now will be the current parent node as in BST the left child node has data value less than the parent node, hence again the conditions at step 1 and step 2 is checked, in this case, all cases satisfy and similarly as in step 2 a new node is created with data value as 5 as the left child node of the parent node 10 and the index is incremented by one, as shown in the above diagram.

4. Now again a recursive call is made to the function with the arguments as the preorder array, the index of the next array element, the minimum number in the range, the maximum number as the current node data value, the next element of the array and the total size of the preorder array traversal.

   

5. Now similarly steps 1 and 2 are repeated and this time as well all conditions are satisfied, and another node is created with data as 1 as the left child node of parent node 5 and the index is incremented by one, as shown in the above diagram.

6. Now again a recursive call is made with the arguments of the preorder array traversal, the index of the next array element, the minimum number in the range, the maximum number as the current node data value, the next element of the preorder array, and the maximum size of the array.

   

7. Now since this time, our second condition becomes ‘False’ and the current data value is not less than the maximum number, so we will return to the right child of the parent node 5 and the node is declared as the right child of the parent node as data value 5, as shown in the above diagram.

8. And the recursive call is made again but to the right child of the parent node with arguments as the preorder array traversal, index to the next element, the data value of the root as the minimum number, maximum number in the range the next data value from the preorder array and the size of the array.

   

9. Now all the conditions are checked, and the tree is formed as shown in the above figure.