Posted on by Kalkicode
Code Recursion

# Construct BST from given preorder traversal using recursion

Constructing a binary search tree (BST) from a given preorder traversal using recursion means creating a binary search tree from an array of elements in the order they would be visited during a preorder traversal of the tree. A binary search tree is a tree data structure where each node has at most two children, and the values in the left subtree of a node are less than the value of the node, and the values in the right subtree are greater than the value of the node.

To construct a BST from a preorder traversal using recursion, the first element in the array will be the root of the BST. We can then recursively build the left and right subtrees by finding the index of the first element that is greater than the root element. The elements before this index will be part of the left subtree, and the elements after this index will be part of the right subtree.

We can then recursively construct the left subtree by calling the function with the subarray containing the elements before the index, and construct the right subtree by calling the function with the subarray containing the elements after the index.

## Program solution

``````/*
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_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_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``````

## 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