Construct BST from given preorder traversal using recursion

Here given code implementation process.

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

 // Tree Node
struct TreeNode
{
	int data;
	struct TreeNode *left;
	struct TreeNode *right;
};
// Binary Search Tree
struct BinarySearchTree
{
	struct TreeNode *root;
};
// 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;
}
struct TreeNode *buildTree(
  		int preorder[], int n, int *index, int min, int max)
{
	if ( *index < n)
	{
		struct TreeNode *node = NULL;
		if (preorder[ *index] >= min && preorder[ *index] <= max)
		{
			node = newTreeNode(preorder[ *index]);
			// Visit to next element
			*index = *index + 1;
			if ( *index < n)
			{
				node->left = buildTree(preorder, 
                                       n, index, min, node->data);
			}
			if ( *index < n)
			{
				node->right = buildTree(preorder, 
                                        n, index, node->data, max);
			}
		}
		return node;
	}
	return NULL;
}
// Handle request to construct bst using given preorder sequence
struct BinarySearchTree *makeTree(int preorder[], int n)
{
	// Create an empty tree
	struct BinarySearchTree *tree = newTree();
	if (n > 0)
	{
		int index = 0;
		tree->root = buildTree(preorder, n, 
                               &index, INT_MIN, INT_MAX);
	}
	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 recursion
class TreeNode
{
    public int data;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int data)
    {
        this.data = data;
        this.left = null;
        this.right = null;
    }
}

 public class BinarySearchTree
 {
    public TreeNode root;
    public int index;
    public BinarySearchTree()
    {
        this.root = null;
        this.index = 0;
    }
    public TreeNode buildTree(
        int[] preorder, int n, 
         int min, int max)
    {
        if (this.index < n)
        {
            TreeNode node = null;
            if (preorder[this.index] >= min && preorder[this.index] <= max)
            {
                node = new TreeNode(preorder[this.index]);
                // Visit to next element
                this.index = this.index + 1;
                if (this.index < n)
                {
                    // Create the left subtree
                    node.left = buildTree(preorder, n, min, node.data);
                }
                if (this.index < n)
                {
                    // Create the right subtree
                    node.right = buildTree(preorder, n, node.data, max);
                }
            }
            return node;
        }
        return null;
    }
    // Handle request to construct bst using given preorder sequence
    public void makeTree(int[] preorder, int n)
    {
        if (n > 0)
        {
            this.index = 0;
            this.root = this.buildTree(preorder, n, Integer.MIN_VALUE , Integer.MAX_VALUE);
        }
    }
    //Display inorder elements
    public void printInorder(TreeNode node)
    {
        if (node != null)
        {
            // Visit left subtree
            printInorder(node.left);
            //Print node value
            System.out.print(" " + node.data );
            // Visit right subtree
            printInorder(node.right);
        }
    }
    //Display preorder elements
    public void printPreorder(TreeNode node)
    {
        if (node != null)
        {
            //Print node value
            System.out.print(" " + node.data);
            // Visit left subtree
            printPreorder(node.left);
            // Visit right subtree
            printPreorder(node.right);
        }
    }
    //Display postorder elements
    public void printPostorder(TreeNode node)
    {
        if (node != null)
        {
            
            // Visit left subtree
            printPostorder(node.left);
            // Visit right subtree
            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 static void main ( String [ ] args )
    {
        BinarySearchTree tree = new BinarySearchTree() ;
        int[] preorder =  {
            15 , 13 , 12 , 11 , 14 , 20 , 19 , 17 , 18 , 21 , 22
        };
        int n = preorder.length;

        tree.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
package main
import "math"
import "fmt"
// Go program for
// Construct BST from given preorder traversal using recursion
type TreeNode struct {
	data int
	left * TreeNode
	right * TreeNode
}
func getTreeNode(data int) * TreeNode {
	var me *TreeNode = &TreeNode {}
	me.data = data
	me.left = nil
	me.right = nil
	return me
}
type BinarySearchTree struct {
	root * TreeNode
	index int
}
func getBinarySearchTree() * BinarySearchTree {
	var me *BinarySearchTree = &BinarySearchTree {}
	me.root = nil
	me.index = 0
	return me
}
func(this *BinarySearchTree) buildTree(preorder[] int, 
	n int, min int, max int) * TreeNode {
	if this.index < n {
		var node * TreeNode = nil
		if preorder[this.index] >= min && preorder[this.index] <= max {
			node = getTreeNode(preorder[this.index])
			// Visit to next element
			this.index = this.index + 1
			if this.index < n {
				// Create the left subtree
				node.left = this.buildTree(preorder, n, min, node.data)
			}
			if this.index < n {
				// Create the right subtree
				node.right = this.buildTree(preorder, n, node.data, max)
			}
		}
		return node
	}
	return nil
}
// Handle request to construct bst using given preorder sequence
func(this *BinarySearchTree) makeTree(preorder[] int, n int) {
	if n > 0 {
		this.index = 0
		this.root = this.buildTree(preorder, n, math.MinInt64, math.MaxInt64)
	}
}
//Display inorder elements
func(this BinarySearchTree) printInorder(node * TreeNode) {
	if node != nil {
		// Visit left subtree
		this.printInorder(node.left)
		//Print node value
		fmt.Print(" ", node.data)
		// Visit right subtree
		this.printInorder(node.right)
	}
}
//Display preorder elements
func(this BinarySearchTree) printPreorder(node * TreeNode) {
	if node != nil {
		//Print node value
		fmt.Print(" ", node.data)
		// Visit left subtree
		this.printPreorder(node.left)
		// Visit right subtree
		this.printPreorder(node.right)
	}
}
//Display postorder elements
func(this BinarySearchTree) printPostorder(node * TreeNode) {
	if node != nil {
		// Visit left subtree
		this.printPostorder(node.left)
		// Visit right subtree
		this.printPostorder(node.right)
		//Print node value
		fmt.Print(" ", node.data)
	}
}
//Handles the request of display the element of tree
func(this BinarySearchTree) printTree() {
	if this.root == nil {
		return
	}
	// Display tree elements in three formats
	fmt.Print("\n Preorder : ")
	this.printPreorder(this.root)
	fmt.Print("\n Inorder : ")
	this.printInorder(this.root)
	fmt.Print("\n Postorder : ")
	this.printPostorder(this.root)
	fmt.Print("\n")
}
func main() {
	var tree * BinarySearchTree = getBinarySearchTree()
	var preorder = [] int {
		15 , 13 , 12 , 11 , 14 , 20 , 19 , 17 , 18 , 21 , 22}
	var n int = len(preorder)
	tree.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>
#include <limits.h>
using namespace std;
// C++ program for
// Construct BST from given preorder traversal using recursion
class TreeNode
{
	public: int data;
	TreeNode *left;
	TreeNode *right;
	TreeNode(int data)
	{
		this->data = data;
		this->left = NULL;
		this->right = NULL;
	}
};
class BinarySearchTree
{
	public: TreeNode *root;
	int index;
	BinarySearchTree()
	{
		this->root = NULL;
		this->index = 0;
	}
	TreeNode *buildTree(int preorder[], int n, int min, int max)
	{
		if (this->index < n)
		{
			TreeNode *node = NULL;
			if (preorder[this->index] >= min && 
                preorder[this->index] <= max)
			{
				node = new TreeNode(preorder[this->index]);
				// Visit to next element
				this->index = this->index + 1;
				if (this->index < n)
				{
					// Create the left subtree
					node->left = this->buildTree(preorder, 
                                                 n, min, node->data);
				}
				if (this->index < n)
				{
					// Create the right subtree
					node->right = this->buildTree(preorder, 
                                                  n, node->data, max);
				}
			}
			return node;
		}
		return NULL;
	}
	// Handle request to construct bst using given preorder sequence
	void makeTree(int preorder[], int n)
	{
		if (n > 0)
		{
			this->index = 0;
			this->root = this->buildTree(preorder, 
                                         n, INT_MIN, INT_MAX);
		}
	}
	//Display inorder elements
	void printInorder(TreeNode *node)
	{
		if (node != NULL)
		{
			// Visit left subtree
			this->printInorder(node->left);
			//Print node value
			cout << " " << node->data;
			// Visit right subtree
			this->printInorder(node->right);
		}
	}
	//Display preorder elements
	void printPreorder(TreeNode *node)
	{
		if (node != NULL)
		{
			//Print node value
			cout << " " << node->data;
			// Visit left subtree
			this->printPreorder(node->left);
			// Visit right subtree
			this->printPreorder(node->right);
		}
	}
	//Display postorder elements
	void printPostorder(TreeNode *node)
	{
		if (node != NULL)
		{
			// Visit left subtree
			this->printPostorder(node->left);
			// Visit right subtree
			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";
	}
};
int main()
{
	BinarySearchTree *tree = new BinarySearchTree();
	int preorder[] = {
		15 , 13 , 12 , 11 , 14 , 20 , 19 , 17 , 18 , 21 , 22
	};
	int n = sizeof(preorder) / sizeof(preorder[0]);
	tree->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;
// Csharp program for
// Construct BST from given preorder traversal using recursion
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;
	}
}
public class BinarySearchTree
{
	public TreeNode root;
	public int index;
	public BinarySearchTree()
	{
		this.root = null;
		this.index = 0;
	}
	public TreeNode buildTree(int[] preorder, int n, int min, int max)
	{
		if (this.index < n)
		{
			TreeNode node = null;
			if (preorder[this.index] >= min && preorder[this.index] <= max)
			{
				node = new TreeNode(preorder[this.index]);
				// Visit to next element
				this.index = this.index + 1;
				if (this.index < n)
				{
					// Create the left subtree
					node.left = this.buildTree(preorder, n, min, node.data);
				}
				if (this.index < n)
				{
					// Create the right subtree
					node.right = this.buildTree(preorder, n, node.data, max);
				}
			}
			return node;
		}
		return null;
	}
	// Handle request to construct bst using given preorder sequence
	public void makeTree(int[] preorder, int n)
	{
		if (n > 0)
		{
			this.index = 0;
			this.root = this.buildTree(preorder, n, int.MinValue, int.MaxValue);
		}
	}
	//Display inorder elements
	public void printInorder(TreeNode node)
	{
		if (node != null)
		{
			// Visit left subtree
			this.printInorder(node.left);
			//Print node value
			Console.Write(" " + node.data);
			// Visit right subtree
			this.printInorder(node.right);
		}
	}
	//Display preorder elements
	public void printPreorder(TreeNode node)
	{
		if (node != null)
		{
			//Print node value
			Console.Write(" " + node.data);
			// Visit left subtree
			this.printPreorder(node.left);
			// Visit right subtree
			this.printPreorder(node.right);
		}
	}
	//Display postorder elements
	public void printPostorder(TreeNode node)
	{
		if (node != null)
		{
			// Visit left subtree
			this.printPostorder(node.left);
			// Visit right subtree
			this.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 : ");
		this.printPreorder(this.root);
		Console.Write("\n Inorder : ");
		this.printInorder(this.root);
		Console.Write("\n Postorder : ");
		this.printPostorder(this.root);
		Console.Write("\n");
	}
	public static void Main(String[] args)
	{
		BinarySearchTree tree = new BinarySearchTree();
		int[] preorder = {
			15 , 13 , 12 , 11 , 14 , 20 , 19 , 17 , 18 , 21 , 22
		};
		int n = preorder.Length;
		tree.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 recursion
class TreeNode
{
	public $data;
	public $left;
	public $right;
	public	function __construct($data)
	{
		$this->data = $data;
		$this->left = NULL;
		$this->right = NULL;
	}
}
class BinarySearchTree
{
	public $root;
	public $index;
	public	function __construct()
	{
		$this->root = NULL;
		$this->index = 0;
	}
	public	function buildTree($preorder, $n, $min, $max)
	{
		if ($this->index < $n)
		{
			$node = NULL;
			if ($preorder[$this->index] >= $min && $preorder[$this->index] <= $max)
			{
				$node = new TreeNode($preorder[$this->index]);
				// Visit to next element
				$this->index = $this->index + 1;
				if ($this->index < $n)
				{
					// Create the left subtree
					$node->left = $this->buildTree(
                      $preorder, $n, $min, $node->data);
				}
				if ($this->index < $n)
				{
					// Create the right subtree
					$node->right = $this->buildTree(
                      $preorder, $n, $node->data, $max);
				}
			}
			return $node;
		}
		return NULL;
	}
	// Handle request to construct bst using given preorder sequence
	public	function makeTree($preorder, $n)
	{
		if ($n > 0)
		{
			$this->index = 0;
			$this->root = $this->buildTree(
              $preorder, $n, -PHP_INT_MAX, PHP_INT_MAX);
		}
	}
	//Display inorder elements
	public	function printInorder($node)
	{
		if ($node != NULL)
		{
			// Visit left subtree
			$this->printInorder($node->left);
			//Print node value
			echo(" ".$node->data);
			// Visit right subtree
			$this->printInorder($node->right);
		}
	}
	//Display preorder elements
	public	function printPreorder($node)
	{
		if ($node != NULL)
		{
			//Print node value
			echo(" ".$node->data);
			// Visit left subtree
			$this->printPreorder($node->left);
			// Visit right subtree
			$this->printPreorder($node->right);
		}
	}
	//Display postorder elements
	public	function printPostorder($node)
	{
		if ($node != NULL)
		{
			// Visit left subtree
			$this->printPostorder($node->left);
			// Visit right subtree
			$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");
	}
}

function main()
{
	$tree = new BinarySearchTree();
	$preorder = array(15, 13, 12, 11, 14, 20, 19, 17, 18, 21, 22);
	$n = count($preorder);
	$tree->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 recursion
class TreeNode
{
	constructor(data)
	{
		this.data = data;
		this.left = null;
		this.right = null;
	}
}
class BinarySearchTree
{
	constructor()
	{
		this.root = null;
		this.index = 0;
	}
	buildTree(preorder, n, min, max)
	{
		if (this.index < n)
		{
			var node = null;
			if (preorder[this.index] >= min && 
                preorder[this.index] <= max)
			{
				node = new TreeNode(preorder[this.index]);
				// Visit to next element
				this.index = this.index + 1;
				if (this.index < n)
				{
					// Create the left subtree
					node.left = this.buildTree(
                      preorder, n, min, node.data);
				}
				if (this.index < n)
				{
					// Create the right subtree
					node.right = this.buildTree(
                      preorder, n, node.data, max);
				}
			}
			return node;
		}
		return null;
	}
	// Handle request to construct bst using given preorder sequence
	makeTree(preorder, n)
	{
		if (n > 0)
		{
			this.index = 0;
			this.root = this.buildTree(preorder, 
                                       n, -Number.MAX_VALUE, 
                                       Number.MAX_VALUE);
		}
	}
	//Display inorder elements
	printInorder(node)
	{
		if (node != null)
		{
			// Visit left subtree
			this.printInorder(node.left);
			//Print node value
			process.stdout.write(" " + node.data);
			// Visit right subtree
			this.printInorder(node.right);
		}
	}
	//Display preorder elements
	printPreorder(node)
	{
		if (node != null)
		{
			//Print node value
			process.stdout.write(" " + node.data);
			// Visit left subtree
			this.printPreorder(node.left);
			// Visit right subtree
			this.printPreorder(node.right);
		}
	}
	//Display postorder elements
	printPostorder(node)
	{
		if (node != null)
		{
			// Visit left subtree
			this.printPostorder(node.left);
			// Visit right subtree
			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");
	}
}

function main()
{
	var tree = new BinarySearchTree();
	var preorder = [15, 13, 12, 11, 14, 20, 19, 17, 18, 21, 22];
	var n = preorder.length;
	tree.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
import sys
#  Python 3 program for
#  Construct BST from given preorder traversal using recursion
class TreeNode :
	def __init__(self, data) :
		self.data = data
		self.left = None
		self.right = None
	

class BinarySearchTree :
	def __init__(self) :
		self.root = None
		self.index = 0
	
	def buildTree(self, preorder, n, min, max) :
		if (self.index < n) :
			node = None
			if (preorder[self.index] >= min and 
                preorder[self.index] <= max) :
				node = TreeNode(preorder[self.index])
				#  Visit to next element
				self.index = self.index + 1
				if (self.index < n) :
					#  Create the left subtree
					node.left = self.buildTree(preorder, n, min, node.data)
				
				if (self.index < n) :
					#  Create the right subtree
					node.right = self.buildTree(preorder, n, node.data, max)
				
			
			return node
		
		return None
	
	#  Handle request to construct bst using given preorder sequence
	def makeTree(self, preorder, n) :
		if (n > 0) :
			self.index = 0
			self.root = self.buildTree(preorder, n, 
                                       -sys.maxsize, sys.maxsize)
		
	
	# Display inorder elements
	def printInorder(self, node) :
		if (node != None) :
			#  Visit left subtree
			self.printInorder(node.left)
			# Print node value
			print(" ", node.data, end = "")
			#  Visit right subtree
			self.printInorder(node.right)
		
	
	# Display preorder elements
	def printPreorder(self, node) :
		if (node != None) :
			# Print node value
			print(" ", node.data, end = "")
			#  Visit left subtree
			self.printPreorder(node.left)
			#  Visit right subtree
			self.printPreorder(node.right)
		
	
	# Display postorder elements
	def printPostorder(self, node) :
		if (node != None) :
			#  Visit left subtree
			self.printPostorder(node.left)
			#  Visit right subtree
			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")
	

def main() :
	tree = BinarySearchTree()
	preorder = [15, 13, 12, 11, 14, 20, 19, 17, 18, 21, 22]
	n = len(preorder)
	tree.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 recursion
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

class BinarySearchTree 
	# Define the accessor and reader of class BinarySearchTree
	attr_reader :root, :index
	attr_accessor :root, :index
	def initialize() 
		self.root = nil
		self.index = 0
	end

	def buildTree(preorder, n, min, max) 
		if (self.index < n) 
			node = nil
			if (preorder[self.index] >= min && preorder[self.index] <= max) 
				node = TreeNode.new(preorder[self.index])
				#  Visit to next element
				self.index = self.index + 1
				if (self.index < n) 
					#  Create the left subtree
					node.left = self.buildTree(preorder, n, min, node.data)
				end

				if (self.index < n) 
					#  Create the right subtree
					node.right = self.buildTree(preorder, n, node.data, max)
				end

			end

			return node
		end

		return nil
	end

	#  Handle request to construct bst using given preorder sequence
	def makeTree(preorder, n) 
		if (n > 0) 
			self.index = 0
			self.root = self.buildTree(preorder, n, 
                                       -(2 ** (0. size * 8 - 2)), 
                                       (2 ** (0. size * 8 - 2)))
		end

	end

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

	end

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

	end

	# Display postorder elements
	def printPostorder(node) 
		if (node != nil) 
			#  Visit left subtree
			self.printPostorder(node.left)
			#  Visit right subtree
			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

def main() 
	tree = BinarySearchTree.new()
	preorder = [15, 13, 12, 11, 14, 20, 19, 17, 18, 21, 22]
	n = preorder.length
	tree.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 recursion
class TreeNode(var data: Int,
	var left: TreeNode,
		var right: TreeNode)
{
	def this(data: Int)
	{
		this(data, null, null);
	}
}
class BinarySearchTree(var root: TreeNode,
	var index: Int)
{
	def this()
	{
		this(null, 0);
	}
	def buildTree(preorder: Array[Int], 
      n: Int, min: Int, max: Int): TreeNode = {
		if (this.index < n)
		{
			var node: TreeNode = null;
			if (preorder(this.index) >= min && 
                preorder(this.index) <= max)
			{
				node = new TreeNode(preorder(this.index));
				// Visit to next element
				this.index = this.index + 1;
				if (this.index < n)
				{
					// Create the left subtree
					node.left = buildTree(preorder, n, min, node.data);
				}
				if (this.index < n)
				{
					// Create the right subtree
					node.right = buildTree(preorder, n, node.data, max);
				}
			}
			return node;
		}
		return null;
	}
	// Handle request to construct bst using given preorder sequence
	def makeTree(preorder: Array[Int], n: Int): Unit = {
		if (n > 0)
		{
			this.index = 0;
			this.root = this.buildTree(preorder, n, 
                                       Int.MinValue, 
                                       Int.MaxValue);
		}
	}
	//Display inorder elements
	def printInorder(node: TreeNode): Unit = {
		if (node != null)
		{
			// Visit left subtree
			printInorder(node.left);
			//Print node value
			print(" " + node.data);
			// Visit right subtree
			printInorder(node.right);
		}
	}
	//Display preorder elements
	def printPreorder(node: TreeNode): Unit = {
		if (node != null)
		{
			//Print node value
			print(" " + node.data);
			// Visit left subtree
			printPreorder(node.left);
			// Visit right subtree
			printPreorder(node.right);
		}
	}
	//Display postorder elements
	def printPostorder(node: TreeNode): Unit = {
		if (node != null)
		{
			// Visit left subtree
			printPostorder(node.left);
			// Visit right subtree
			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 : ");
		printPreorder(this.root);
		print("\n Inorder : ");
		printInorder(this.root);
		print("\n Postorder : ");
		printPostorder(this.root);
		print("\n");
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		var tree: BinarySearchTree = new BinarySearchTree();
		var preorder: Array[Int] = Array(
          15, 13, 12, 11, 14, 20, 19, 17, 18, 21, 22);
		var n: Int = preorder.length;
		tree.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
import Foundation;
// Swift 4 program for
// Construct BST from given preorder traversal using recursion
class TreeNode
{
	var data: Int;
	var left: TreeNode? ;
	var right: TreeNode? ;
	init(_ data: Int)
	{
		self.data = data;
		self.left = nil;
		self.right = nil;
	}
}
class BinarySearchTree
{
	var root: TreeNode? ;
	var index: Int;
	init()
	{
		self.root = nil;
		self.index = 0;
	}
	func buildTree(_ preorder: [Int], 
      _ n: Int, 
        _ min: Int, 
          _ max: Int) -> TreeNode?
	{
		if (self.index < n)
		{
			var node: TreeNode? = nil;
			if (preorder[self.index] >= min && 
              preorder[self.index] <= max)
			{
				node = TreeNode(preorder[self.index]);
				// Visit to next element
				self.index = self.index + 1;
				if (self.index < n)
				{
					// Create the left subtree
					node!.left = self.buildTree(
                      preorder, n, min, node!.data);
				}
				if (self.index < n)
				{
					// Create the right subtree
					node!.right = self.buildTree(
                      preorder, n, node!.data, max);
				}
			}
			return node;
		}
		return nil;
	}
	// Handle request to construct bst using given preorder sequence
	func makeTree(_ preorder: [Int], _ n: Int)
	{
		if (n > 0)
		{
			self.index = 0;
			self.root = self.buildTree(preorder, n, Int.min, Int.max);
		}
	}
	//Display inorder elements
	func printInorder(_ node: TreeNode? )
	{
		if (node  != nil)
		{
			// Visit left subtree
			self.printInorder(node!.left);
			//Print node value
			print(" ", node!.data, terminator: "");
			// Visit right subtree
			self.printInorder(node!.right);
		}
	}
	//Display preorder elements
	func printPreorder(_ node: TreeNode? )
	{
		if (node  != nil)
		{
			//Print node value
			print(" ", node!.data, terminator: "");
			// Visit left subtree
			self.printPreorder(node!.left);
			// Visit right subtree
			self.printPreorder(node!.right);
		}
	}
	//Display postorder elements
	func printPostorder(_ node: TreeNode? )
	{
		if (node  != nil)
		{
			// Visit left subtree
			self.printPostorder(node!.left);
			// Visit right subtree
			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");
	}
}
func main()
{
	let tree: BinarySearchTree = BinarySearchTree();
	let preorder: [Int] = [15, 13, 12, 11, 14, 20, 19, 17, 18, 21, 22];
	let n: Int = preorder.count;
	tree.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 recursion
class TreeNode
{
	var data: Int;
	var left: TreeNode ? ;
	var right: TreeNode ? ;
	constructor(data: Int)
	{
		this.data = data;
		this.left = null;
		this.right = null;
	}
}
class BinarySearchTree
{
	var root: TreeNode ? ;
	var index: Int;
	constructor()
	{
		this.root = null;
		this.index = 0;
	}
	fun buildTree(preorder: Array < Int > , 
                  n: Int, min: Int, max: Int): TreeNode ?
	{
		if (this.index < n)
		{
			var node: TreeNode ? = null;
			if (preorder[this.index] >= min && 
              preorder[this.index] <= max)
			{
				node = TreeNode(preorder[this.index]);
				// Visit to next element
				this.index = this.index + 1;
				if (this.index < n)
				{
					// Create the left subtree
					node.left = this.buildTree(
                    preorder, n, min, node.data);
				}
				if (this.index < n)
				{
					// Create the right subtree
					node.right = this.buildTree(
                    preorder, n, node.data, max);
				}
			}
			return node;
		}
		return null;
	}
	// Handle request to construct bst using given preorder sequence
	fun makeTree(preorder: Array < Int > , n: Int): Unit
	{
		if (n > 0)
		{
			this.index = 0;
			this.root = this.buildTree(preorder, 
                                       n, Int.MIN_VALUE, 
                                       Int.MAX_VALUE);
		}
	}
	//Display inorder elements
	fun printInorder(node: TreeNode ? ): Unit
	{
		if (node != null)
		{
			// Visit left subtree
			this.printInorder(node.left);
			//Print node value
			print(" " + node.data);
			// Visit right subtree
			this.printInorder(node.right);
		}
	}
	//Display preorder elements
	fun printPreorder(node: TreeNode ? ): Unit
	{
		if (node != null)
		{
			//Print node value
			print(" " + node.data);
			// Visit left subtree
			this.printPreorder(node.left);
			// Visit right subtree
			this.printPreorder(node.right);
		}
	}
	//Display postorder elements
	fun printPostorder(node: TreeNode ? ): Unit
	{
		if (node != null)
		{
			// Visit left subtree
			this.printPostorder(node.left);
			// Visit right subtree
			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");
	}
}
fun main(args: Array < String > ): Unit
{
	val tree: BinarySearchTree = BinarySearchTree();
	val preorder: Array < Int > = arrayOf(15, 13, 12, 11, 14, 20, 19, 17, 18, 21, 22);
	val n: Int = preorder.count();
	tree.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