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 15package 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 15import 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 15import 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