Construct BST from given preorder traversal using stack

Here given code implementation process.

/*
    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;
    }

    // Add stack element
    stack->top = node;
    stack->size++;
}
// return top element of stack
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]);
            //  Add stack element
            push(st,node->right);
        }
        else
        {
            // Get the  top element of stack
            node = peek(st); 

            // Add node in left subtree
            node->left = newTreeNode(preorder[i]);
            //  Add stack element
            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--;
        }
    }
    // return top element of stack
    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]);
                //  Add stack element
                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]);
                //  Add stack element
                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;
        Construct task = new Construct();

        BinarySearchTree tree = 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
// 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--;
		}
	}
	// return top element of stack
	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]);
					//  Add stack element
					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]);
					//  Add stack element
					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]);
	Construct task = Construct();
	BinarySearchTree *tree = task.makeTree(preorder, n);
	/*
	            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--;
		}
	}
	// return top element of stack
	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]);
				//  Add stack element
				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]);
				//  Add stack element
				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;
		Construct task = new Construct();
		BinarySearchTree tree = 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
<?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--;
		}
	}
	// return top element of stack
	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]);
				//  Add stack element
				$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]);
				//  Add stack element
				$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);
	$task = new Construct();
	$tree = $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
/*
   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--;
		}
	}
	// return top element of stack
	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]);
				//  Add stack element
				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]);
				//  Add stack element
				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;
	var task = new Construct();
	var tree = 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
#    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
		
	
	#  return top element of stack
	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])
				#   Add stack element
				st.push(node.right)
			else :
				#  Get the  top element of stack
				node = st.peek()
				#  Add node in left subtree
				node.left = TreeNode(preorder[i])
				#   Add stack element
				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)
	task = Construct()
	tree = task.makeTree(preorder, n)
	# 
	#             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_reader :data, :left, :right
	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_reader :element, :next
	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_reader :top, :size
	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

	#  return top element of stack
	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_reader :root
	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])
				#   Add stack element
				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])
				#   Add stack element
				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
	task = Construct.new()
	tree = task.makeTree(preorder, n)
	# 
	#             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;
		}
	}
	// return top element of stack
	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));
				//  Add stack element
				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));
				//  Add stack element
				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;
		}
	}
	// return top element of stack
	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]);
				//  Add stack element
				st.push(node!.right);
			}
			else
			{
				// Get the  top element of stack
				node = st.peek();
				// Add node in left subtree
				node!.left = TreeNode(preorder[i]);
				//  Add stack element
				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 task: Construct = Construct();
	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;
		}
	}
	// return top element of stack
	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]);
				//  Add stack element
				st.push(node.right);
			}
			else
			{
				// Get the  top element of stack
				node = st.peek();
				// Add node in left subtree
				node?.left = TreeNode(preorder[i]);
				//  Add stack element
				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 task: Construct = 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


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.

New Comment







© 2021, kalkicode.com, All rights reserved