Posted on by Kalkicode
Code Stack

# Construct BST from given preorder traversal using stack

The task is to construct a Binary Search Tree (BST) from the given preorder traversal of the tree using a stack data structure.

## Problem Statement

Given a preorder traversal of a Binary Search Tree (BST), the task is to construct the corresponding BST and display its elements in preorder, inorder, and postorder.

## Example

Consider the following preorder traversal of a BST:

``preorder = [15, 13, 12, 11, 14, 20, 19, 17, 18, 21, 22]``

The BST that can be constructed from the given preorder traversal is as follows:

``````
15
/     \
13      20
/  \     / \
12  14   19  21
/        /      \
11      17      22
\
18
``````

The elements of the BST in different orders are:

• Preorder: 15 13 12 11 14 20 19 17 18 21 22
• Inorder: 11 12 13 14 15 17 18 19 20 21 22
• Postorder: 11 12 14 13 18 17 19 22 21 20 15

## Idea to Solve the Problem

To construct a BST from the given preorder traversal, we can use a stack data structure to keep track of the nodes of the tree while traversing the preorder array. We start by creating the root node from the first element of the preorder array. Then, we iterate through the remaining elements of the array and use a stack to maintain the nodes that we have encountered so far.

1. Initialize an empty stack and create the root node of the BST using the first element of the preorder array.
2. Iterate through the remaining elements of the preorder array from index 1 to n-1 (where n is the number of elements in the preorder array).
3. For each element, check if it is less than the value of the top element of the stack. a. If yes, then it is the left child of the top element of the stack. Push it into the stack as the left child. b. If no, then it is the right child of one of the nodes in the stack. Pop elements from the stack until the top element is greater than the current element. The last popped element is the parent of the current element. Push the current element as the right child of the last popped element.
4. Continue the iteration until all elements are processed.
5. The BST is constructed.

## Pseudocode

``````Function makeTree(preorder, n):
If n <= 0, return null
Create an empty tree called 'tree'
Create an empty stack called 'stack'
Create the root node of the tree using the first element of the preorder array
Push the root node into the stack
Set 'i' as 1
While i < n:
Create a new node called 'node' with value preorder[i]
Set 'temp' as null
While stack is not empty and stack.top.data < preorder[i]:
Set 'temp' as stack.pop()
If temp is not null:
Set temp.right as 'node'
Else:
Set stack.top.left as 'node'
Push 'node' into the stack
Increment 'i' by 1
Return 'tree'
``````

## Algorithm

1. Create an empty BST called `tree`.
2. Create an empty stack called `stack`.
3. Create the root node of the BST using the first element of the `preorder` array and assign it to the `root` of the `tree`.
4. Push the root node into the stack.
5. Start iterating through the remaining elements of the `preorder` array from index 1 to n-1. a. For each element, create a new node `node` with the value of the current element. b. Set `temp` as null. c. While the stack is not empty and the value of the top element of the stack (i.e., `stack.top.data`) is less than the current element (`preorder[i]`), pop elements from the stack and set `temp` as the popped element. d. If `temp` is not null, set `temp.right` as `node`, as the current element is the right child of `temp`. e. If `temp` is null, set `stack.top.left` as `node`, as the current element is the left child of the top element of the stack. f. Push `node` into the stack. g. Increment `i` by 1.
6. Return the `tree`, which is now the constructed BST.

## Code Solution

``````/*
C Program
Construct BST from given preorder traversal using stack
*/
#include <stdio.h>
#include <stdlib.h>

// Tree Node
struct TreeNode
{
int data;
struct TreeNode *left;
struct TreeNode *right;
};

// Binary Search Tree
struct BinarySearchTree
{
struct TreeNode *root;
};

// Define stack node
struct StackNode
{
struct TreeNode * element;
struct StackNode *next;
};
// Define a custom stack
struct MyStack
{
struct StackNode *top;
int size;
};

struct MyStack *newStack()
{
//Make a stack
struct MyStack *stack = (struct MyStack *) malloc(sizeof(struct MyStack));
if (stack != NULL)
{
//Set node values
stack->top = NULL;
stack->size = 0;
}
else
{
printf("\nMemory overflow when create new stack\n");
}
}
// Returns the status of empty or non empty stacks
int isEmpty(struct MyStack *stack)
{
if (stack->size > 0 && stack->top != NULL)
{
return 0;
}
else
{
return 1;
}
}
// Add node at the top of stack
void push(struct MyStack *stack, struct TreeNode* element)
{

// Make a new node
struct StackNode *node = (struct StackNode *) malloc(sizeof(struct StackNode));
if (node == NULL)
{
printf("\nMemory overflow when create new stack Node \n");
}
else
{
node->element = element;
node->next    = stack->top;
}

stack->top = node;
stack->size++;
}
struct TreeNode * peek(struct MyStack *stack)
{
if(stack->top == NULL)
{
return NULL;
}
return stack->top->element;
}
// Remove top element of stack
void pop(struct MyStack *stack)
{
if (isEmpty(stack) == 0)
{
struct StackNode *temp = stack->top;
// Change top element of stack
stack->top = temp->next;
// remove previous top
free(temp);
temp = NULL;
stack->size--;
}
}

// Create new tree
struct BinarySearchTree *newTree()
{
// Create dynamic node
struct BinarySearchTree *tree = (struct BinarySearchTree *) malloc(sizeof(struct BinarySearchTree));

if (tree != NULL)
{
tree->root = NULL;
}
else
{
printf("Memory Overflow to Create tree Tree\n");
}
// return new tree
return tree;
}
// returns a new node of tree
struct TreeNode *newTreeNode(int data)
{
// Create dynamic node
struct TreeNode *node = (struct TreeNode *) malloc(sizeof(struct TreeNode));
if (node != NULL)
{
//Set data and pointer values
node->data = data;
node->left = NULL;
node->right = NULL;
}
else
{
//This is indicates, segmentation fault or memory overflow problem
printf("Memory Overflow\n");
}
//return new node
return node;
}
// Handle request to construct bst using given preorder sequence
struct BinarySearchTree *makeTree(int preorder[],int n)
{
if(n <= 0)
{
return NULL;
}
// Create an empty tree
struct BinarySearchTree *tree = newTree();

// Create an empty stack
struct MyStack* st = newStack();

// Create first node of tree
struct TreeNode* node = newTreeNode(preorder[0]);

// Add first element into stack
push(st,node);

tree->root = node;

int i = 1;

while(i < n)
{

node = NULL;
// Find new inserted node position
while(isEmpty(st)==0 && peek(st)->data < preorder[i] )
{
// Get the  top element of stack
node =  peek(st);
// Remove top element of stack
pop(st);
}

if(node!=NULL)
{
// Add node in right subtree
node->right = newTreeNode(preorder[i]);
push(st,node->right);
}
else
{
// Get the  top element of stack
node = peek(st);

// Add node in left subtree
node->left = newTreeNode(preorder[i]);
push(st,node->left);
}

i++;
}

return tree;
}

//Display inorder elements
void printInorder(struct TreeNode *node)
{
if (node != NULL)
{
printInorder(node->left);
//Print node value
printf("  %d", node->data);
printInorder(node->right);
}
}
//Display pre order elements
void printPreorder(struct TreeNode *node)
{
if (node != NULL)
{
//Print node value
printf("  %d", node->data);
printPreorder(node->left);
printPreorder(node->right);
}
}
//Display postorder elements
void printPostorder(struct TreeNode *node)
{
if (node != NULL)
{
printPostorder(node->left);
printPostorder(node->right);
//Print node value
printf("  %d", node->data);
}
}
//Handles the request of display the element of tree
void printTree(struct TreeNode *root)
{
if (root == NULL)
{
return;
}
// Display tree elements in three formats
printf("\n Preorder : ");
printPreorder(root);
printf("\n Inorder : ");
printInorder(root);
printf("\n Postorder : ");
printPostorder(root);
printf("\n");
}
int main()
{
int preorder[] = {15,13,12,11,14,20,19,17,18,21,22};

int n = sizeof(preorder)/sizeof(preorder[0]);

struct BinarySearchTree *tree = makeTree(preorder, n);
/*
15
/     \
13      20
/  \     / \
12  14   19  21
/        /      \
11       17       22
\
18
-----------------------
Built binary search tree
*/
printTree(tree->root);

return 0;
}``````

#### Output

`````` Preorder :   15  13  12  11  14  20  19  17  18  21  22
Inorder :   11  12  13  14  15  17  18  19  20  21  22
Postorder :   11  12  14  13  18  17  19  22  21  20  15``````
``````/*
Java Program for
Construct BST from given preorder traversal using stack
*/
class TreeNode
{
public int data;
public TreeNode left;
public TreeNode right;
public TreeNode(int data)
{
this.data = data;
this.left = null;
this.right = null;
}
}
// Define stack node
class StackNode
{
public TreeNode element;
public StackNode next;
public StackNode(TreeNode element, StackNode top)
{
this.element = element;
this.next = top;
}
}
// Define a custom stack
class MyStack
{
public StackNode top;
public int size;
public MyStack()
{
//Set node values
this.top = null;
this.size = 0;
}
// Add node at the top of stack
public void push(TreeNode element)
{
this.top = new StackNode(element, this.top);
this.size++;
}
public boolean isEmpty()
{
if (this.size > 0 && this.top != null)
{
return false;
}
else
{
return true;
}
}
// Remove top element of stack
public void pop()
{
if (this.size > 0 && this.top != null)
{
StackNode temp = this.top;
// Change top element of stack
this.top = temp.next;
// remove previous top
temp = null;
this.size--;
}
}
public TreeNode peek()
{
if (this.top == null)
{
return null;
}
return this.top.element;
}
}
class BinarySearchTree
{
public TreeNode root;
public BinarySearchTree()
{
this.root = null;
}
//Display inorder elements
public void printInorder(TreeNode node)
{
if (node != null)
{
printInorder(node.left);
//Print node value
System.out.print(" " + node.data);
printInorder(node.right);
}
}
//Display pre order elements
public void printPreorder(TreeNode node)
{
if (node != null)
{
//Print node value
System.out.print(" " + node.data);
printPreorder(node.left);
printPreorder(node.right);
}
}
//Display postorder elements
public void printPostorder(TreeNode node)
{
if (node != null)
{
printPostorder(node.left);
printPostorder(node.right);
//Print node value
System.out.print(" " + node.data);
}
}
//Handles the request of display the element of tree
public void printTree()
{
if (this.root == null)
{
return;
}
// Display tree elements in three formats
System.out.print("\n Preorder :");
printPreorder(this.root);
System.out.print("\n Inorder :");
printInorder(this.root);
System.out.print("\n Postorder :");
printPostorder(this.root);
System.out.print("\n");
}

}
public class Construct
{

// Handle request to construct bst using given preorder sequence
public BinarySearchTree makeTree(int[] preorder, int n)
{
if (n <= 0)
{
return null;
}
// Create an empty tree
BinarySearchTree tree = new BinarySearchTree();
// Create an empty stack
MyStack st = new MyStack();
// Create first node of tree
TreeNode node = new TreeNode(preorder[0]);
// Add first element into stack
st.push(node);
tree.root = node;
int i = 1;
while (i < n)
{
node = null;
// Find new inserted node position
while (st.isEmpty() == false && st.peek().data < preorder[i])
{
// Get the  top element of stack
node = st.peek();
// Remove top element of stack
st.pop();
}
if (node != null)
{
// Add node in right subtree
node.right = new TreeNode(preorder[i]);
st.push(node.right);
}
else
{
// Get the  top element of stack
node = st.peek();
// Add node in left subtree
node.left = new TreeNode(preorder[i]);
st.push(node.left);
}
i++;
}
return tree;
}
public static void main(String[] args)
{

int[] preorder = {
15 , 13 , 12 , 11 , 14 , 20 , 19 , 17 , 18 , 21 , 22
};
int n = preorder.length;

/*
15
/     \
13      20
/  \     / \
12  14   19  21
/        /      \
11       17       22
\
18
-----------------------
Built binary search tree
*/
tree.printTree();
}
}``````

#### Output

`````` Preorder : 15 13 12 11 14 20 19 17 18 21 22
Inorder : 11 12 13 14 15 17 18 19 20 21 22
Postorder : 11 12 14 13 18 17 19 22 21 20 15``````
``````// Include header file
#include <iostream>

using namespace std;
/*
C++ Program for
Construct BST from given preorder traversal using stack
*/
class TreeNode
{
public: int data;
TreeNode *left;
TreeNode *right;
TreeNode(int data)
{
this->data = data;
this->left = NULL;
this->right = NULL;
}
};
// Define stack node
class StackNode
{
public: TreeNode *element;
StackNode *next;
StackNode(TreeNode *element, StackNode *top)
{
this->element = element;
this->next = top;
}
};
// Define a custom stack
class MyStack
{
public: StackNode *top;
int size;
MyStack()
{
//Set node values
this->top = NULL;
this->size = 0;
}
// Add node at the top of stack
void push(TreeNode *element)
{
this->top = new StackNode(element, this->top);
this->size++;
}
bool isEmpty()
{
if (this->size > 0 && this->top != NULL)
{
return false;
}
else
{
return true;
}
}
// Remove top element of stack
void pop()
{
if (this->size > 0 && this->top != NULL)
{
StackNode *temp = this->top;
// Change top element of stack
this->top = temp->next;
// remove previous top
temp = NULL;
this->size--;
}
}
TreeNode *peek()
{
if (this->top == NULL)
{
return NULL;
}
return this->top->element;
}
};
class BinarySearchTree
{
public: TreeNode *root;
BinarySearchTree()
{
this->root = NULL;
}
//Display inorder elements
void printInorder(TreeNode *node)
{
if (node != NULL)
{
this->printInorder(node->left);
//Print node value
cout << " " << node->data;
this->printInorder(node->right);
}
}
//Display pre order elements
void printPreorder(TreeNode *node)
{
if (node != NULL)
{
//Print node value
cout << " " << node->data;
this->printPreorder(node->left);
this->printPreorder(node->right);
}
}
//Display postorder elements
void printPostorder(TreeNode *node)
{
if (node != NULL)
{
this->printPostorder(node->left);
this->printPostorder(node->right);
//Print node value
cout << " " << node->data;
}
}
//Handles the request of display the element of tree
void printTree()
{
if (this->root == NULL)
{
return;
}
// Display tree elements in three formats
cout << "\n Preorder :";
this->printPreorder(this->root);
cout << "\n Inorder :";
this->printInorder(this->root);
cout << "\n Postorder :";
this->printPostorder(this->root);
cout << "\n";
}
};
class Construct
{
public:
// Handle request to construct bst using given preorder sequence
BinarySearchTree *makeTree(int preorder[], int n)
{
if (n <= 0)
{
return NULL;
}
// Create an empty tree
BinarySearchTree *tree = new BinarySearchTree();
// Create an empty stack
MyStack st = MyStack();
// Create first node of tree
TreeNode *node = new TreeNode(preorder[0]);
// Add first element into stack
st.push(node);
tree->root = node;
int i = 1;
while (i < n)
{
node = NULL;
// Find new inserted node position
while (st.isEmpty() == false && st.peek()->data < preorder[i])
{
// Get the  top element of stack
node = st.peek();
// Remove top element of stack
st.pop();
}
if (node != NULL)
{
// Add node in right subtree
node->right = new TreeNode(preorder[i]);
st.push(node->right);
}
else
{
// Get the  top element of stack
node = st.peek();
// Add node in left subtree
node->left = new TreeNode(preorder[i]);
st.push(node->left);
}
i++;
}
return tree;
}
};
int main()
{
int preorder[] = {
15 , 13 , 12 , 11 , 14 , 20 , 19 , 17 , 18 , 21 , 22
};
int n = sizeof(preorder) / sizeof(preorder[0]);
/*
15
/     \
13      20
/  \     / \
12  14   19  21
/        /      \
11       17       22
\
18
-----------------------
Built binary search tree
*/
tree->printTree();
return 0;
}``````

#### Output

`````` Preorder : 15 13 12 11 14 20 19 17 18 21 22
Inorder : 11 12 13 14 15 17 18 19 20 21 22
Postorder : 11 12 14 13 18 17 19 22 21 20 15``````
``````// Include namespace system
using System;
/*
C# Program for
Construct BST from given preorder traversal using stack
*/
public class TreeNode
{
public int data;
public TreeNode left;
public TreeNode right;
public TreeNode(int data)
{
this.data = data;
this.left = null;
this.right = null;
}
}
// Define stack node
public class StackNode
{
public TreeNode element;
public StackNode next;
public StackNode(TreeNode element, StackNode top)
{
this.element = element;
this.next = top;
}
}
// Define a custom stack
public class MyStack
{
public StackNode top;
public int size;
public MyStack()
{
//Set node values
this.top = null;
this.size = 0;
}
// Add node at the top of stack
public void push(TreeNode element)
{
this.top = new StackNode(element, this.top);
this.size++;
}
public Boolean isEmpty()
{
if (this.size > 0 && this.top != null)
{
return false;
}
else
{
return true;
}
}
// Remove top element of stack
public void pop()
{
if (this.size > 0 && this.top != null)
{
StackNode temp = this.top;
// Change top element of stack
this.top = temp.next;
// remove previous top
temp = null;
this.size--;
}
}
public TreeNode peek()
{
if (this.top == null)
{
return null;
}
return this.top.element;
}
}
public class BinarySearchTree
{
public TreeNode root;
public BinarySearchTree()
{
this.root = null;
}
//Display inorder elements
public void printInorder(TreeNode node)
{
if (node != null)
{
printInorder(node.left);
//Print node value
Console.Write(" " + node.data);
printInorder(node.right);
}
}
//Display pre order elements
public void printPreorder(TreeNode node)
{
if (node != null)
{
//Print node value
Console.Write(" " + node.data);
printPreorder(node.left);
printPreorder(node.right);
}
}
//Display postorder elements
public void printPostorder(TreeNode node)
{
if (node != null)
{
printPostorder(node.left);
printPostorder(node.right);
//Print node value
Console.Write(" " + node.data);
}
}
//Handles the request of display the element of tree
public void printTree()
{
if (this.root == null)
{
return;
}
// Display tree elements in three formats
Console.Write("\n Preorder :");
printPreorder(this.root);
Console.Write("\n Inorder :");
printInorder(this.root);
Console.Write("\n Postorder :");
printPostorder(this.root);
Console.Write("\n");
}
}
public class Construct
{
// Handle request to construct bst using given preorder sequence
public BinarySearchTree makeTree(int[] preorder, int n)
{
if (n <= 0)
{
return null;
}
// Create an empty tree
BinarySearchTree tree = new BinarySearchTree();
// Create an empty stack
MyStack st = new MyStack();
// Create first node of tree
TreeNode node = new TreeNode(preorder[0]);
// Add first element into stack
st.push(node);
tree.root = node;
int i = 1;
while (i < n)
{
node = null;
// Find new inserted node position
while (st.isEmpty() == false && st.peek().data < preorder[i])
{
// Get the  top element of stack
node = st.peek();
// Remove top element of stack
st.pop();
}
if (node != null)
{
// Add node in right subtree
node.right = new TreeNode(preorder[i]);
st.push(node.right);
}
else
{
// Get the  top element of stack
node = st.peek();
// Add node in left subtree
node.left = new TreeNode(preorder[i]);
st.push(node.left);
}
i++;
}
return tree;
}
public static void Main(String[] args)
{
int[] preorder = {
15 , 13 , 12 , 11 , 14 , 20 , 19 , 17 , 18 , 21 , 22
};
int n = preorder.Length;
/*
15
/     \
13      20
/  \     / \
12  14   19  21
/        /      \
11       17       22
\
18
-----------------------
Built binary search tree
*/
tree.printTree();
}
}``````

#### Output

`````` Preorder : 15 13 12 11 14 20 19 17 18 21 22
Inorder : 11 12 13 14 15 17 18 19 20 21 22
Postorder : 11 12 14 13 18 17 19 22 21 20 15``````
``````<?php
/*
Php Program for
Construct BST from given preorder traversal using stack
*/
class TreeNode
{
public \$data;
public \$left;
public \$right;

function __construct(\$data)
{
\$this->data = \$data;
\$this->left = null;
\$this->right = null;
}
}
// Define stack node
class StackNode
{
public \$element;
public \$next;

function __construct(\$element, \$top)
{
\$this->element = \$element;
\$this->next = \$top;
}
}
// Define a custom stack
class MyStack
{
public \$top;
public \$size;

function __construct()
{
//Set node values
\$this->top = null;
\$this->size = 0;
}
// Add node at the top of stack
public	function push(\$element)
{
\$this->top = new StackNode(\$element, \$this->top);
\$this->size++;
}
public	function isEmpty()
{
if (\$this->size > 0 && \$this->top != null)
{
return false;
}
else
{
return true;
}
}
// Remove top element of stack
public	function pop()
{
if (\$this->size > 0 && \$this->top != null)
{
\$temp = \$this->top;
// Change top element of stack
\$this->top = \$temp->next;
// remove previous top
\$temp = null;
\$this->size--;
}
}
public	function peek()
{
if (\$this->top == null)
{
return null;
}
return \$this->top->element;
}
}
class BinarySearchTree
{
public \$root;

function __construct()
{
\$this->root = null;
}
//Display inorder elements
public	function printInorder(\$node)
{
if (\$node != null)
{
\$this->printInorder(\$node->left);
//Print node value
echo " ". \$node->data;
\$this->printInorder(\$node->right);
}
}
//Display pre order elements
public	function printPreorder(\$node)
{
if (\$node != null)
{
//Print node value
echo " ". \$node->data;
\$this->printPreorder(\$node->left);
\$this->printPreorder(\$node->right);
}
}
//Display postorder elements
public	function printPostorder(\$node)
{
if (\$node != null)
{
\$this->printPostorder(\$node->left);
\$this->printPostorder(\$node->right);
//Print node value
echo " ". \$node->data;
}
}
//Handles the request of display the element of tree
public	function printTree()
{
if (\$this->root == null)
{
return;
}
// Display tree elements in three formats
echo "\n Preorder :";
\$this->printPreorder(\$this->root);
echo "\n Inorder :";
\$this->printInorder(\$this->root);
echo "\n Postorder :";
\$this->printPostorder(\$this->root);
echo "\n";
}
}
class Construct
{
// Handle request to construct bst using given preorder sequence
public	function makeTree( & \$preorder, \$n)
{
if (\$n <= 0)
{
return null;
}
// Create an empty tree
\$tree = new BinarySearchTree();
// Create an empty stack
\$st = new MyStack();
// Create first node of tree
\$node = new TreeNode(\$preorder[0]);
// Add first element into stack
\$st->push(\$node);
\$tree->root = \$node;
\$i = 1;
while (\$i < \$n)
{
\$node = null;
// Find new inserted node position
while (\$st->isEmpty() == false && \$st->peek()->data < \$preorder[\$i])
{
// Get the  top element of stack
\$node = \$st->peek();
// Remove top element of stack
\$st->pop();
}
if (\$node != null)
{
// Add node in right subtree
\$node->right = new TreeNode(\$preorder[\$i]);
\$st->push(\$node->right);
}
else
{
// Get the  top element of stack
\$node = \$st->peek();
// Add node in left subtree
\$node->left = new TreeNode(\$preorder[\$i]);
\$st->push(\$node->left);
}
\$i++;
}
return \$tree;
}
}

function main()
{
\$preorder = array(15, 13, 12, 11, 14, 20, 19, 17, 18, 21, 22);
\$n = count(\$preorder);
/*
15
/     \
13      20
/  \     / \
12  14   19  21
/        /      \
11       17       22
\
18
-----------------------
Built binary search tree
*/
\$tree->printTree();
}
main();``````

#### Output

`````` Preorder : 15 13 12 11 14 20 19 17 18 21 22
Inorder : 11 12 13 14 15 17 18 19 20 21 22
Postorder : 11 12 14 13 18 17 19 22 21 20 15``````
``````/*
Node Js Program for
Construct BST from given preorder traversal using stack
*/
class TreeNode
{
constructor(data)
{
this.data = data;
this.left = null;
this.right = null;
}
}
// Define stack node
class StackNode
{
constructor(element, top)
{
this.element = element;
this.next = top;
}
}
// Define a custom stack
class MyStack
{
constructor()
{
//Set node values
this.top = null;
this.size = 0;
}
// Add node at the top of stack
push(element)
{
this.top = new StackNode(element, this.top);
this.size++;
}
isEmpty()
{
if (this.size > 0 && this.top != null)
{
return false;
}
else
{
return true;
}
}
// Remove top element of stack
pop()
{
if (this.size > 0 && this.top != null)
{
var temp = this.top;
// Change top element of stack
this.top = temp.next;
// remove previous top
temp = null;
this.size--;
}
}
peek()
{
if (this.top == null)
{
return null;
}
return this.top.element;
}
}
class BinarySearchTree
{
constructor()
{
this.root = null;
}
//Display inorder elements
printInorder(node)
{
if (node != null)
{
this.printInorder(node.left);
//Print node value
process.stdout.write(" " + node.data);
this.printInorder(node.right);
}
}
//Display pre order elements
printPreorder(node)
{
if (node != null)
{
//Print node value
process.stdout.write(" " + node.data);
this.printPreorder(node.left);
this.printPreorder(node.right);
}
}
//Display postorder elements
printPostorder(node)
{
if (node != null)
{
this.printPostorder(node.left);
this.printPostorder(node.right);
//Print node value
process.stdout.write(" " + node.data);
}
}
//Handles the request of display the element of tree
printTree()
{
if (this.root == null)
{
return;
}
// Display tree elements in three formats
process.stdout.write("\n Preorder :");
this.printPreorder(this.root);
process.stdout.write("\n Inorder :");
this.printInorder(this.root);
process.stdout.write("\n Postorder :");
this.printPostorder(this.root);
process.stdout.write("\n");
}
}
class Construct
{
// Handle request to construct bst using given preorder sequence
makeTree(preorder, n)
{
if (n <= 0)
{
return null;
}
// Create an empty tree
var tree = new BinarySearchTree();
// Create an empty stack
var st = new MyStack();
// Create first node of tree
var node = new TreeNode(preorder[0]);
// Add first element into stack
st.push(node);
tree.root = node;
var i = 1;
while (i < n)
{
node = null;
// Find new inserted node position
while (st.isEmpty() == false && st.peek().data < preorder[i])
{
// Get the  top element of stack
node = st.peek();
// Remove top element of stack
st.pop();
}
if (node != null)
{
// Add node in right subtree
node.right = new TreeNode(preorder[i]);
st.push(node.right);
}
else
{
// Get the  top element of stack
node = st.peek();
// Add node in left subtree
node.left = new TreeNode(preorder[i]);
st.push(node.left);
}
i++;
}
return tree;
}
}

function main()
{
var preorder = [15, 13, 12, 11, 14, 20, 19, 17, 18, 21, 22];
var n = preorder.length;
/*
15
/     \
13      20
/  \     / \
12  14   19  21
/        /      \
11       17       22
\
18
-----------------------
Built binary search tree
*/
tree.printTree();
}
main();``````

#### Output

`````` Preorder : 15 13 12 11 14 20 19 17 18 21 22
Inorder : 11 12 13 14 15 17 18 19 20 21 22
Postorder : 11 12 14 13 18 17 19 22 21 20 15``````
``````#    Python 3 Program for
#    Construct BST from given preorder traversal using stack

class TreeNode :

def __init__(self, data) :
self.data = data
self.left = None
self.right = None

#  Define stack node
class StackNode :

def __init__(self, element, top) :
self.element = element
self.next = top

#  Define a custom stack
class MyStack :

def __init__(self) :
# Set node values
self.top = None
self.size = 0

#  Add node at the top of stack
def push(self, element) :
self.top = StackNode(element, self.top)
self.size += 1

def isEmpty(self) :
if (self.size > 0 and self.top != None) :
return False
else :
return True

#  Remove top element of stack
def pop(self) :
if (self.size > 0 and self.top != None) :
temp = self.top
#  Change top element of stack
self.top = temp.next
#  remove previous top
temp = None
self.size -= 1

def peek(self) :
if (self.top == None) :
return None

return self.top.element

class BinarySearchTree :

def __init__(self) :
self.root = None

# Display inorder elements
def printInorder(self, node) :
if (node != None) :
self.printInorder(node.left)
# Print node value
print(" ", node.data, end = "")
self.printInorder(node.right)

# Display pre order elements
def printPreorder(self, node) :
if (node != None) :
# Print node value
print(" ", node.data, end = "")
self.printPreorder(node.left)
self.printPreorder(node.right)

# Display postorder elements
def printPostorder(self, node) :
if (node != None) :
self.printPostorder(node.left)
self.printPostorder(node.right)
# Print node value
print(" ", node.data, end = "")

# Handles the request of display the element of tree
def printTree(self) :
if (self.root == None) :
return

#  Display tree elements in three formats
print("\n Preorder :", end = "")
self.printPreorder(self.root)
print("\n Inorder :", end = "")
self.printInorder(self.root)
print("\n Postorder :", end = "")
self.printPostorder(self.root)
print(end = "\n")

class Construct :
#  Handle request to construct bst using given preorder sequence
def makeTree(self, preorder, n) :
if (n <= 0) :
return None

#  Create an empty tree
tree = BinarySearchTree()
#  Create an empty stack
st = MyStack()
#  Create first node of tree
node = TreeNode(preorder[0])
#  Add first element into stack
st.push(node)
tree.root = node
i = 1
while (i < n) :
node = None
#  Find new inserted node position
while (st.isEmpty() == False and st.peek().data < preorder[i]) :
#  Get the  top element of stack
node = st.peek()
#  Remove top element of stack
st.pop()

if (node != None) :
#  Add node in right subtree
node.right = TreeNode(preorder[i])
st.push(node.right)
else :
#  Get the  top element of stack
node = st.peek()
#  Add node in left subtree
node.left = TreeNode(preorder[i])
st.push(node.left)

i += 1

return tree

def main() :
preorder = [15, 13, 12, 11, 14, 20, 19, 17, 18, 21, 22]
n = len(preorder)
#
#             15
#          /     \
#         13      20
#        /  \     / \
#       12  14   19  21
#      /        /      \
#     11       17       22
#               \
#                18
#     -----------------------
#     Built binary search tree

tree.printTree()

if __name__ == "__main__": main()``````

#### Output

`````` Preorder :  15  13  12  11  14  20  19  17  18  21  22
Inorder :  11  12  13  14  15  17  18  19  20  21  22
Postorder :  11  12  14  13  18  17  19  22  21  20  15``````
``````#    Ruby Program for
#    Construct BST from given preorder traversal using stack

class TreeNode
# Define the accessor and reader of class TreeNode
attr_accessor :data, :left, :right

def initialize(data)
self.data = data
self.left = nil
self.right = nil
end

end

#  Define stack node
class StackNode
# Define the accessor and reader of class StackNode
attr_accessor :element, :next

def initialize(element, top)
self.element = element
self.next = top
end

end

#  Define a custom stack
class MyStack
# Define the accessor and reader of class MyStack
attr_accessor :top, :size

def initialize()
# Set node values
self.top = nil
self.size = 0
end

#  Add node at the top of stack
def push(element)
self.top = StackNode.new(element, self.top)
self.size += 1
end

def isEmpty()
if (self.size > 0 && self.top != nil)
return false
else
return true
end

end

#  Remove top element of stack
def pop()
if (self.size > 0 && self.top != nil)
temp = self.top
#  Change top element of stack
self.top = temp.next
#  remove previous top
temp = nil
self.size -= 1
end

end

def peek()
if (self.top == nil)
return nil
end

return self.top.element
end

end

class BinarySearchTree
# Define the accessor and reader of class BinarySearchTree
attr_accessor :root

def initialize()
self.root = nil
end

# Display inorder elements
def printInorder(node)
if (node != nil)
self.printInorder(node.left)
# Print node value
print(" ", node.data)
self.printInorder(node.right)
end

end

# Display pre order elements
def printPreorder(node)
if (node != nil)
# Print node value
print(" ", node.data)
self.printPreorder(node.left)
self.printPreorder(node.right)
end

end

# Display postorder elements
def printPostorder(node)
if (node != nil)
self.printPostorder(node.left)
self.printPostorder(node.right)
# Print node value
print(" ", node.data)
end

end

# Handles the request of display the element of tree
def printTree()
if (self.root == nil)
return
end

#  Display tree elements in three formats
print("\n Preorder :")
self.printPreorder(self.root)
print("\n Inorder :")
self.printInorder(self.root)
print("\n Postorder :")
self.printPostorder(self.root)
print("\n")
end

end

class Construct
#  Handle request to construct bst using given preorder sequence
def makeTree(preorder, n)
if (n <= 0)
return nil
end

#  Create an empty tree
tree = BinarySearchTree.new()
#  Create an empty stack
st = MyStack.new()
#  Create first node of tree
node = TreeNode.new(preorder[0])
#  Add first element into stack
st.push(node)
tree.root = node
i = 1
while (i < n)
node = nil
#  Find new inserted node position
while (st.isEmpty() == false && st.peek().data < preorder[i])
#  Get the  top element of stack
node = st.peek()
#  Remove top element of stack
st.pop()
end

if (node != nil)
#  Add node in right subtree
node.right = TreeNode.new(preorder[i])
st.push(node.right)
else
#  Get the  top element of stack
node = st.peek()
#  Add node in left subtree
node.left = TreeNode.new(preorder[i])
st.push(node.left)
end

i += 1
end

return tree
end

end

def main()
preorder = [15, 13, 12, 11, 14, 20, 19, 17, 18, 21, 22]
n = preorder.length
#
#             15
#          /     \
#         13      20
#        /  \     / \
#       12  14   19  21
#      /        /      \
#     11       17       22
#               \
#                18
#     -----------------------
#     Built binary search tree

tree.printTree()
end

main()``````

#### Output

`````` Preorder : 15 13 12 11 14 20 19 17 18 21 22
Inorder : 11 12 13 14 15 17 18 19 20 21 22
Postorder : 11 12 14 13 18 17 19 22 21 20 15
``````
``````/*
Scala Program for
Construct BST from given preorder traversal using stack
*/
class TreeNode(var data: Int , var left: TreeNode , var right: TreeNode)
{
def this(data: Int)
{
this(data, null, null);
}
}
// Define stack node
class StackNode(var element: TreeNode , var next: StackNode);
// Define a custom stack
class MyStack(var top: StackNode , var size: Int)
{
def this()
{
this(null, 0);
}
// Add node at the top of stack
def push(element: TreeNode): Unit = {
this.top = new StackNode(element, this.top);
this.size += 1;
}
def isEmpty(): Boolean = {
if (this.size > 0 && this.top != null)
{
return false;
}
else
{
return true;
}
}
// Remove top element of stack
def pop(): Unit = {
if (this.size > 0 && this.top != null)
{
var temp: StackNode = this.top;
// Change top element of stack
this.top = temp.next;
// remove previous top
temp = null;
this.size -= 1;
}
}
def peek(): TreeNode = {
if (this.top == null)
{
return null;
}
return this.top.element;
}
}
class BinarySearchTree(var root: TreeNode)
{
def this()
{
this(null);
}
//Display inorder elements
def printInorder(node: TreeNode): Unit = {
if (node != null)
{
this.printInorder(node.left);
//Print node value
print(" " + node.data);
this.printInorder(node.right);
}
}
//Display pre order elements
def printPreorder(node: TreeNode): Unit = {
if (node != null)
{
//Print node value
print(" " + node.data);
this.printPreorder(node.left);
this.printPreorder(node.right);
}
}
//Display postorder elements
def printPostorder(node: TreeNode): Unit = {
if (node != null)
{
this.printPostorder(node.left);
this.printPostorder(node.right);
//Print node value
print(" " + node.data);
}
}
//Handles the request of display the element of tree
def printTree(): Unit = {
if (this.root == null)
{
return;
}
// Display tree elements in three formats
print("\n Preorder :");
this.printPreorder(this.root);
print("\n Inorder :");
this.printInorder(this.root);
print("\n Postorder :");
this.printPostorder(this.root);
print("\n");
}
}
class Construct
{
// Handle request to construct bst using given preorder sequence
def makeTree(preorder: Array[Int], n: Int): BinarySearchTree = {
if (n <= 0)
{
return null;
}
// Create an empty tree
var tree: BinarySearchTree = new BinarySearchTree();
// Create an empty stack
var st: MyStack = new MyStack();
// Create first node of tree
var node: TreeNode = new TreeNode(preorder(0));
// Add first element into stack
st.push(node);
tree.root = node;
var i: Int = 1;
while (i < n)
{
node = null;
// Find new inserted node position
while (st.isEmpty() == false && st.peek().data < preorder(i))
{
// Get the  top element of stack
node = st.peek();
// Remove top element of stack
st.pop();
}
if (node != null)
{
// Add node in right subtree
node.right = new TreeNode(preorder(i));
st.push(node.right);
}
else
{
// Get the  top element of stack
node = st.peek();
// Add node in left subtree
node.left = new TreeNode(preorder(i));
st.push(node.left);
}
i += 1;
}
return tree;
}
}
object Main
{
def main(args: Array[String]): Unit = {
var preorder: Array[Int] = Array(15, 13, 12, 11, 14, 20, 19, 17, 18, 21, 22);
var n: Int = preorder.length;
var task: Construct = new Construct();
var tree: BinarySearchTree = task.makeTree(preorder, n);
/*
15
/     \
13      20
/  \     / \
12  14   19  21
/        /      \
11       17       22
\
18
-----------------------
Built binary search tree
*/
tree.printTree();
}
}``````

#### Output

`````` Preorder : 15 13 12 11 14 20 19 17 18 21 22
Inorder : 11 12 13 14 15 17 18 19 20 21 22
Postorder : 11 12 14 13 18 17 19 22 21 20 15``````
``````/*
Swift 4 Program for
Construct BST from given preorder traversal using stack
*/
class TreeNode
{
var data: Int;
var left: TreeNode? ;
var right: TreeNode? ;
init(_ data: Int)
{
self.data = data;
self.left = nil;
self.right = nil;
}
}
// Define stack node
class StackNode
{
var element: TreeNode? ;
var next: StackNode? ;
init(_ element: TreeNode? , _ top : StackNode? )
{
self.element = element;
self.next = top;
}
}
// Define a custom stack
class MyStack
{
var top: StackNode? ;
var size: Int;
init()
{
//Set node values
self.top = nil;
self.size = 0;
}
// Add node at the top of stack
func push(_ element: TreeNode? )
{
self.top = StackNode(element, self.top);
self.size += 1;
}
func isEmpty()->Bool
{
if (self.size > 0 && self.top  != nil)
{
return false;
}
else
{
return true;
}
}
// Remove top element of stack
func pop()
{
if (self.size > 0 && self.top  != nil)
{
var temp: StackNode? = self.top;
// Change top element of stack
self.top = temp!.next;
// remove previous top
temp = nil;
self.size -= 1;
}
}
func peek()->TreeNode?
{
if (self.top == nil)
{
return nil;
}
return self.top!.element;
}
}
class BinarySearchTree
{
var root: TreeNode? ;
init()
{
self.root = nil;
}
//Display inorder elements
func printInorder(_ node: TreeNode? )
{
if (node  != nil)
{
self.printInorder(node!.left);
//Print node value
print(" ", node!.data, terminator: "");
self.printInorder(node!.right);
}
}
//Display pre order elements
func printPreorder(_ node: TreeNode? )
{
if (node  != nil)
{
//Print node value
print(" ", node!.data, terminator: "");
self.printPreorder(node!.left);
self.printPreorder(node!.right);
}
}
//Display postorder elements
func printPostorder(_ node: TreeNode? )
{
if (node  != nil)
{
self.printPostorder(node!.left);
self.printPostorder(node!.right);
//Print node value
print(" ", node!.data, terminator: "");
}
}
//Handles the request of display the element of tree
func printTree()
{
if (self.root == nil)
{
return;
}
// Display tree elements in three formats
print("\n Preorder :", terminator: "");
self.printPreorder(self.root);
print("\n Inorder :", terminator: "");
self.printInorder(self.root);
print("\n Postorder :", terminator: "");
self.printPostorder(self.root);
print(terminator: "\n");
}
}
class Construct
{
// Handle request to construct bst using given preorder sequence
func makeTree(_ preorder: [Int], _ n: Int)->BinarySearchTree?
{
if (n <= 0)
{
return nil;
}
// Create an empty tree
let tree: BinarySearchTree? = BinarySearchTree();
// Create an empty stack
let st: MyStack = MyStack();
// Create first node of tree
var node: TreeNode? = TreeNode(preorder[0]);
// Add first element into stack
st.push(node);
tree!.root = node;
var i: Int = 1;
while (i < n)
{
node = nil;
// Find new inserted node position
while (st.isEmpty() == false && st.peek()!.data < preorder[i])
{
// Get the  top element of stack
node = st.peek();
// Remove top element of stack
st.pop();
}
if (node  != nil)
{
// Add node in right subtree
node!.right = TreeNode(preorder[i]);
st.push(node!.right);
}
else
{
// Get the  top element of stack
node = st.peek();
// Add node in left subtree
node!.left = TreeNode(preorder[i]);
st.push(node!.left);
}
i += 1;
}
return tree;
}
}
func main()
{
let preorder: [Int] = [15, 13, 12, 11, 14, 20, 19, 17, 18, 21, 22];
let n: Int = preorder.count;
let tree: BinarySearchTree? = task.makeTree(preorder, n);
/*
15
/     \
13      20
/  \     / \
12  14   19  21
/        /      \
11       17       22
\
18
-----------------------
Built binary search tree
*/
tree!.printTree();
}
main();``````

#### Output

`````` Preorder :  15  13  12  11  14  20  19  17  18  21  22
Inorder :  11  12  13  14  15  17  18  19  20  21  22
Postorder :  11  12  14  13  18  17  19  22  21  20  15``````
``````/*
Kotlin Program for
Construct BST from given preorder traversal using stack
*/
class TreeNode
{
var data: Int;
var left: TreeNode ? ;
var right: TreeNode ? ;
constructor(data: Int)
{
this.data = data;
this.left = null;
this.right = null;
}
}
// Define stack node
class StackNode
{
var element: TreeNode ? ;
var next: StackNode ? ;
constructor(element: TreeNode ? , top : StackNode ? )
{
this.element = element;
this.next = top;
}
}
// Define a custom stack
class MyStack
{
var top: StackNode ? ;
var size: Int;
constructor()
{
//Set node values
this.top = null;
this.size = 0;
}
// Add node at the top of stack
fun push(element: TreeNode ? ): Unit
{
this.top = StackNode(element, this.top);
this.size += 1;
}
fun isEmpty(): Boolean
{
if (this.size > 0 && this.top != null)
{
return false;
}
else
{
return true;
}
}
// Remove top element of stack
fun pop(): Unit
{
if (this.size > 0 && this.top != null)
{
var temp: StackNode ? = this.top;
// Change top element of stack
this.top = temp?.next;
this.size -= 1;
}
}
fun peek(): TreeNode ?
{
if (this.top == null)
{
return null;
}
return this.top?.element;
}
}
class BinarySearchTree
{
var root: TreeNode ? ;
constructor()
{
this.root = null;
}
//Display inorder elements
fun printInorder(node: TreeNode ? ): Unit
{
if (node != null)
{
this.printInorder(node.left);
//Print node value
print(" " + node.data);
this.printInorder(node.right);
}
}
//Display pre order elements
fun printPreorder(node: TreeNode ? ): Unit
{
if (node != null)
{
//Print node value
print(" " + node.data);
this.printPreorder(node.left);
this.printPreorder(node.right);
}
}
//Display postorder elements
fun printPostorder(node: TreeNode ? ): Unit
{
if (node != null)
{
this.printPostorder(node.left);
this.printPostorder(node.right);
//Print node value
print(" " + node.data);
}
}
//Handles the request of display the element of tree
fun printTree(): Unit
{
if (this.root == null)
{
return;
}
// Display tree elements in three formats
print("\n Preorder :");
this.printPreorder(this.root);
print("\n Inorder :");
this.printInorder(this.root);
print("\n Postorder :");
this.printPostorder(this.root);
print("\n");
}
}
class Construct
{
// Handle request to construct bst using given preorder sequence
fun makeTree(preorder: Array < Int > , n: Int): BinarySearchTree
{
// Create an empty tree
var tree: BinarySearchTree = BinarySearchTree();
if (n <= 0)
{
return tree;
}

// Create an empty stack
var st: MyStack = MyStack();
// Create first node of tree
var node: TreeNode ? = TreeNode(preorder[0]);
// Add first element into stack
st.push(node);
tree.root = node;
var i: Int = 1;
while (i < n)
{
node = null;
// Find new inserted node position
while (st.isEmpty() == false && st.peek()!!.data < preorder[i])
{
// Get the  top element of stack
node = st.peek();
// Remove top element of stack
st.pop();
}
if (node != null)
{
// Add node in right subtree
node.right = TreeNode(preorder[i]);
st.push(node.right);
}
else
{
// Get the  top element of stack
node = st.peek();
// Add node in left subtree
node?.left = TreeNode(preorder[i]);
st.push(node?.left);
}
i += 1;
}
return tree;
}
}
fun main(args: Array < String > ): Unit
{
var preorder: Array <Int> = arrayOf(15, 13, 12, 11, 14, 20, 19, 17, 18, 21, 22);
var n: Int = preorder.count();
var tree: BinarySearchTree? = task.makeTree(preorder, n);
/*
15
/     \
13      20
/  \     / \
12  14   19  21
/        /      \
11       17       22
\
18
-----------------------
Built binary search tree
*/
tree?.printTree();
}``````

#### Output

`````` Preorder : 15 13 12 11 14 20 19 17 18 21 22
Inorder : 11 12 13 14 15 17 18 19 20 21 22
Postorder : 11 12 14 13 18 17 19 22 21 20 15``````

## Time Complexity

The time complexity of the algorithm is O(n), where n is the number of elements in the preorder array. The algorithm processes each element once, and the stack operations are also performed in constant time for each element. Therefore, the time complexity is linear with respect to the number of elements in the preorder array.

## Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

Categories
Relative Post