Construct Binary Search Tree from Preorder in c++

 

Construct Binary Search Tree from Preorder

A binary search tree (BST) is a popular data structure that is used to efficiently store and retrieve data. One of the ways to construct a BST is by using preorder traversal. In this method, the first element of the preorder traversal is the root of the tree, and the elements that follow are used to construct the left and right subtrees. In this article, we will discuss how to construct a binary search tree from preorder traversal using C++.

Before we dive into the implementation, let's first understand the preorder traversal of a binary search tree. In preorder traversal, we visit the root node first, followed by the left subtree and then the right subtree. This is done by traversing the left subtree first and then the right subtree. The preorder traversal of a binary search tree can be represented as the root, left, right order.

The algorithm to construct a BST from preorder traversal is as follows:

  1. Create a new empty stack.
  2. Initialize the root of the tree to be the first element of the preorder traversal.
  3. Iterate through the remaining elements of the preorder traversal.
  4. If the current element is less than the top of the stack, it is the left child of the node at the top of the stack.
  5. If the current element is greater than the top of the stack, pop the stack until the current element is less than the top of the stack. The popped nodes will become the right child of the last popped node.
  6. Push the current element onto the stack.
  7. Repeat steps 4-6 until all elements have been processed.

Let's now implement this algorithm in C++. We will create a class called "BST" that contains the functions for creating the tree and preorder traversal.

class BST
{ 
 public:
 int data; 
 BST *left, *right;
 BST(int data);
 BST* constructBST(int preorder[], int size);
 void preorderTraversal(BST *root);
 };

The constructor of the class initializes the data and left and right pointers to null. The function "constructBST" takes an array of integers and its size as input, and returns the root of the constructed BST. The function "preorderTraversal" takes the root of the tree as input and prints the preorder traversal of the tree.

BST::BST(int data)
 {
 this->data = data;
 left = right = NULL;
 }

BST* BST::constructBST(int preorder[], int size)
{
 stack<BST*> stk;
    BST* root = new BST(preorder[0]); 
 stk.push(root);
 for (int i = 1; i < size; i++)
    {
 BST* temp = NULL;
 while (!stk.empty() && preorder[i] > stk.top()->data)
        {
 temp = stk.top();
 stk.pop();
 }
 if (temp != NULL)
        {
 temp->right = new BST(preorder[i]);
 stk.push(temp->right); 
 } 
 else
        {
 temp = stk.top();
 temp->left = new BST(preorder
[i]);
stk.push(temp->left);
}
}

return root;



In this function, we first create a new stack and push the first element of the preorder traversal, which is the root of the tree, onto the stack. We then iterate through the remaining elements of the preorder traversal. If the current element is less than the top of the stack, it is the left child of the node at the top of the stack. If the current element is greater than the top of the stack, we pop the stack until the current element is less than the top of the stack. The popped nodes will become the right child of the last popped node. We then push the current element onto the stack. We repeat this process until all elements have been processed.

void BST::preorderTraversal(BST* root) { if (root != NULL) { cout << root->data << " "; preorderTraversal(root->left); preorderTraversal(root->right); } }


This function takes the root of the tree as input and prints the preorder traversal of the tree by recursively visiting the root, left subtree and then the right subtree. 
 Now, let's test our implementation by creating a BST from a preorder traversal and then printing its preorder traversal.

int main() { int preorder[] = {8, 5, 1, 7, 10, 12}; int size = sizeof(preorder) / sizeof(preorder[0]);

BST* root = constructBST(preorder, size); 
 cout << "Preorder Traversal of BST: ";
 preorderTraversal(root);
 return 0;

}


In this example, we create a BST from the preorder traversal {8, 5, 1, 7, 10, 12} and then print its preorder traversal. The output should be "8 5 1 7 10 12", which is the same as the input preorder traversal.

In conclusion, constructing a binary search tree from preorder traversal is a useful technique for efficiently storing and retrieving data. By using a stack to keep track of the current node, we can easily navigate through the tree and construct it in a way that preserves its binary search tree properties. With this implementation, we can easily construct a binary search tree from preorder traversal in C++.
csadda

Posted by csadda