Construct BST from level order traversal
Here given code implementation process.
//C Program
//Construct BST from level order traversal
#include <stdio.h>
#include <stdlib.h>
//structure of Binary Search Tree node
struct Node
{
int data;
struct Node *left, *right;
};
//Adding a new node in binary search tree
void add_node(struct Node **root, int data)
{
//Create a dynamic node of binary search tree
struct Node *new_node = (struct Node *) malloc(sizeof(struct Node));
if (new_node != NULL)
{
//Set data and pointer values
new_node->data = data;
new_node->left = NULL; //Initially node left-pointer is NULL
new_node->right = NULL; //Initially node right-pointer is NULL
if ( *root == NULL)
{
//When adds a first node in binary tree
*root = new_node;
}
else
{
struct Node *find = *root;
//iterate binary tree and add new node to proper position
while (find != NULL)
{
if (find->data > data)
{
if (find->left == NULL)
{
find->left = new_node;
break;
}
else
{ //visit left sub-tree
find = find->left;
}
}
else
{
if (find->right == NULL)
{
find->right = new_node;
break;
}
else
{
//visit right sub-tree
find = find->right;
}
}
}
}
}
else
{
printf("Memory Overflow\n");
exit(0); //Terminate program execution
}
}
//Construct BST using level order data
struct Node *level_order_insert(int level_data[], int size)
{
struct Node *local_root = NULL;
//first check its number of elements
if (size > 0)
{
//When array are not empty
for (int i = 0; i < size; ++i)
{
//Add element into tree
add_node( & local_root, level_data[i]);
}
}
return local_root;
}
//Preorder tree traversal
void preorder(struct Node *root)
{
if (root != NULL)
{
printf("%3d ", root->data);
preorder(root->left);
preorder(root->right);
}
}
//Inorder tree traversal
void inorder(struct Node *root)
{
if (root != NULL)
{
inorder(root->left);
printf("%3d ", root->data);
inorder(root->right);
}
}
//Postorder tree traversal
void postorder(struct Node *root)
{
if (root != NULL)
{
postorder(root->left);
postorder(root->right);
printf("%3d ", root->data);
}
}
int main()
{
struct Node *root = NULL;
//Add nodes in binary search tree
/*
5
/ \
3 9
/ \ / \
1 4 8 11
/ \ / \
0 2 7 12
*/
int level_data[] = {
5 , 3 , 9 , 1 , 4 , 8 , 11 , 0 , 2 , 7 , 12
};
int size = sizeof(level_data) / sizeof(level_data[0]);
root = level_order_insert(level_data, size);
printf("\nPerorder : ");
preorder(root);
printf("\nInorder : ");
inorder(root);
printf("\nPostorder : ");
postorder(root);
return 0;
}
Output
Perorder : 5 3 1 0 2 4 9 8 7 11 12
Inorder : 0 1 2 3 4 5 7 8 9 11 12
Postorder : 0 2 1 4 3 7 8 12 11 9 5
//Java program
//Construct BST from level order traversal
//Binary Tree Node
class Node
{
public int data;
public Node left;
public Node right;
public Node(int data)
{
this.data = data;
this.left = null;
this.right = null;
}
}
class BinarySearchTree
{
public Node root;
//Class constructors
public BinarySearchTree()
{
root = null;
}
//insert element
public void add_node(int data)
{
//Create a new binary tree node
Node new_node = new Node(data);
if (new_node != null)
{
if (this.root == null)
{
//When adds a first node in binary tree
this.root = new_node;
}
else
{
Node find = this.root;
//add new node to proper position
while (find != null)
{
if (find.data >= data)
{
if (find.left == null)
{
find.left = new_node;
break;
}
else
{
//visit left sub-tree
find = find.left;
}
}
else
{
if (find.right == null)
{
find.right = new_node;
break;
}
else
{
//visit right sub-tree
find = find.right;
}
}
}
}
}
else
{
System.out.println("Memory Overflow");
}
}
public void preorder(Node root)
{
if (root != null)
{
System.out.print(" " + root.data);
preorder(root.left);
preorder(root.right);
}
}
public void inorder(Node root)
{
if (root != null)
{
inorder(root.left);
System.out.print(" " + root.data);
inorder(root.right);
}
}
public void postorder(Node root)
{
if (root != null)
{
postorder(root.left);
postorder(root.right);
System.out.print(" " + root.data);
}
}
//Construct BST using level order data
public void level_order_insert(int[] level_data, int size)
{
//first check its number of elements
if (size > 0)
{
//When array are not empty
for (int i = 0; i < size; ++i)
{
//Add element into tree
add_node(level_data[i]);
}
}
}
public static void main(String[] args)
{
BinarySearchTree obj = new BinarySearchTree();
int[] level_data = {
5 , 3 , 9 , 1 , 4 , 8 , 11 , 0 , 2 , 7 , 12
};
int size = level_data.length;
obj.level_order_insert(level_data, size);
System.out.print("\nPerorder : ");
obj.preorder(obj.root);
System.out.print("\nInorder : ");
obj.inorder(obj.root);
System.out.print("\nPostorder : ");
obj.postorder(obj.root);
}
}
Output
Perorder : 5 3 1 0 2 4 9 8 7 11 12
Inorder : 0 1 2 3 4 5 7 8 9 11 12
Postorder : 0 2 1 4 3 7 8 12 11 9 5
//Include header file
#include <iostream>
using namespace std;
//C++ program
//Construct BST from level order traversal
//Binary Tree Node
class Node
{
public:
int data;
Node * left;
Node * right;
Node(int data)
{
this->data = data;
this->left = NULL;
this->right = NULL;
}
};
class BinarySearchTree
{
public: Node * root;
//Class constructors
BinarySearchTree()
{
this->root = NULL;
}
//insert element
void add_node(int data)
{
//Create a new binary tree node
Node * new_node = new Node(data);
if (new_node != NULL)
{
if (this->root == NULL)
{
//When adds a first node in binary tree
this->root = new_node;
}
else
{
Node * find = this->root;
//add new node to proper position
while (find != NULL)
{
if (find->data >= data)
{
if (find->left == NULL)
{
find->left = new_node;
break;
}
else
{
//visit left sub-tree
find = find->left;
}
}
else
{
if (find->right == NULL)
{
find->right = new_node;
break;
}
else
{
//visit right sub-tree
find = find->right;
}
}
}
}
}
else
{
cout << "Memory Overflow";
}
}
void preorder(Node * root)
{
if (root != NULL)
{
cout << " " << root->data;
this->preorder(root->left);
this->preorder(root->right);
}
}
void inorder(Node * root)
{
if (root != NULL)
{
this->inorder(root->left);
cout << " " << root->data;
this->inorder(root->right);
}
}
void postorder(Node * root)
{
if (root != NULL)
{
this->postorder(root->left);
this->postorder(root->right);
cout << " " << root->data;
}
}
//Construct BST using level order data
void level_order_insert(int level_data[], int size)
{
//first check its number of elements
if (size > 0)
{
//When array are not empty
for (int i = 0; i < size; ++i)
{
//Add element into tree
this->add_node(level_data[i]);
}
}
}
};
int main()
{
BinarySearchTree obj = BinarySearchTree();
int level_data[] = {
5 , 3 , 9 , 1 , 4 , 8 , 11 , 0 , 2 , 7 , 12
};
int size = sizeof(level_data) / sizeof(level_data[0]);
obj.level_order_insert(level_data, size);
cout << "\nPerorder : ";
obj.preorder(obj.root);
cout << "\nInorder : ";
obj.inorder(obj.root);
cout << "\nPostorder : ";
obj.postorder(obj.root);
return 0;
}
Output
Perorder : 5 3 1 0 2 4 9 8 7 11 12
Inorder : 0 1 2 3 4 5 7 8 9 11 12
Postorder : 0 2 1 4 3 7 8 12 11 9 5
//Include namespace system
using System;
//C# program
//Construct BST from level order traversal
//Binary Tree Node
public class Node
{
public int data;
public Node left;
public Node right;
public Node(int data)
{
this.data = data;
this.left = null;
this.right = null;
}
}
public class BinarySearchTree
{
public Node root;
//Class constructors
public BinarySearchTree()
{
root = null;
}
//insert element
public void add_node(int data)
{
//Create a new binary tree node
Node new_node = new Node(data);
if (new_node != null)
{
if (this.root == null)
{
//When adds a first node in binary tree
this.root = new_node;
}
else
{
Node find = this.root;
//add new node to proper position
while (find != null)
{
if (find.data >= data)
{
if (find.left == null)
{
find.left = new_node;
break;
}
else
{
//visit left sub-tree
find = find.left;
}
}
else
{
if (find.right == null)
{
find.right = new_node;
break;
}
else
{
//visit right sub-tree
find = find.right;
}
}
}
}
}
else
{
Console.WriteLine("Memory Overflow");
}
}
public void preorder(Node root)
{
if (root != null)
{
Console.Write(" " + root.data);
preorder(root.left);
preorder(root.right);
}
}
public void inorder(Node root)
{
if (root != null)
{
inorder(root.left);
Console.Write(" " + root.data);
inorder(root.right);
}
}
public void postorder(Node root)
{
if (root != null)
{
postorder(root.left);
postorder(root.right);
Console.Write(" " + root.data);
}
}
//Construct BST using level order data
public void level_order_insert(int[] level_data, int size)
{
//first check its number of elements
if (size > 0)
{
//When array are not empty
for (int i = 0; i < size; ++i)
{
//Add element into tree
add_node(level_data[i]);
}
}
}
public static void Main(String[] args)
{
BinarySearchTree obj = new BinarySearchTree();
int[] level_data = {
5 , 3 , 9 , 1 , 4 , 8 , 11 , 0 , 2 , 7 , 12
};
int size = level_data.Length;
obj.level_order_insert(level_data, size);
Console.Write("\nPerorder : ");
obj.preorder(obj.root);
Console.Write("\nInorder : ");
obj.inorder(obj.root);
Console.Write("\nPostorder : ");
obj.postorder(obj.root);
}
}
Output
Perorder : 5 3 1 0 2 4 9 8 7 11 12
Inorder : 0 1 2 3 4 5 7 8 9 11 12
Postorder : 0 2 1 4 3 7 8 12 11 9 5
<?php
//Php program
//Construct BST from level order traversal
//Binary Tree Node
class Node
{
public $data;
public $left;
public $right;
function __construct($data)
{
$this->data = $data;
$this->left = null;
$this->right = null;
}
}
class BinarySearchTree
{
public $root;
//Class constructors
function __construct()
{
$this->root = null;
}
//insert element
public function add_node($data)
{
//Create a new binary tree node
$new_node = new Node($data);
if ($new_node != null)
{
if ($this->root == null)
{
//When adds a first node in binary tree
$this->root = $new_node;
}
else
{
$find = $this->root;
//add new node to proper position
while ($find != null)
{
if ($find->data >= $data)
{
if ($find->left == null)
{
$find->left = $new_node;
break;
}
else
{
//visit left sub-tree
$find = $find->left;
}
}
else
{
if ($find->right == null)
{
$find->right = $new_node;
break;
}
else
{
//visit right sub-tree
$find = $find->right;
}
}
}
}
}
else
{
echo "Memory Overflow";
}
}
public function preorder($root)
{
if ($root != null)
{
echo " ". $root->data;
$this->preorder($root->left);
$this->preorder($root->right);
}
}
public function inorder($root)
{
if ($root != null)
{
$this->inorder($root->left);
echo " ". $root->data;
$this->inorder($root->right);
}
}
public function postorder($root)
{
if ($root != null)
{
$this->postorder($root->left);
$this->postorder($root->right);
echo " ". $root->data;
}
}
//Construct BST using level order data
public function level_order_insert( & $level_data, $size)
{
//first check its number of elements
if ($size > 0)
{
//When array are not empty
for ($i = 0; $i < $size; ++$i)
{
//Add element into tree
$this->add_node($level_data[$i]);
}
}
}
}
function main()
{
$obj = new BinarySearchTree();
$level_data = array(5, 3, 9, 1, 4, 8, 11, 0, 2, 7, 12);
$size = count($level_data);
$obj->level_order_insert($level_data, $size);
echo "\nPerorder : ";
$obj->preorder($obj->root);
echo "\nInorder : ";
$obj->inorder($obj->root);
echo "\nPostorder : ";
$obj->postorder($obj->root);
}
main();
Output
Perorder : 5 3 1 0 2 4 9 8 7 11 12
Inorder : 0 1 2 3 4 5 7 8 9 11 12
Postorder : 0 2 1 4 3 7 8 12 11 9 5
# Python 3 program
# Construct BST from level order traversal
# Binary Tree Node
class Node :
def __init__(self, data) :
self.data = data
self.left = None
self.right = None
class BinarySearchTree :
# Class constructors
def __init__(self) :
self.root = None
# insert element
def add_node(self, data) :
# Create a new binary tree node
new_node = Node(data)
if (new_node != None) :
if (self.root == None) :
# When adds a first node in binary tree
self.root = new_node
else :
find = self.root
# add new node to proper position
while (find != None) :
if (find.data >= data) :
if (find.left == None) :
find.left = new_node
break
else :
# visit left sub-tree
find = find.left
else :
if (find.right == None) :
find.right = new_node
break
else :
# visit right sub-tree
find = find.right
else :
print("Memory Overflow", end = "")
def preorder(self, root) :
if (root != None) :
print(" ", root.data, end = "")
self.preorder(root.left)
self.preorder(root.right)
def inorder(self, root) :
if (root != None) :
self.inorder(root.left)
print(" ", root.data, end = "")
self.inorder(root.right)
def postorder(self, root) :
if (root != None) :
self.postorder(root.left)
self.postorder(root.right)
print(" ", root.data, end = "")
# Construct BST using level order data
def level_order_insert(self, level_data, size) :
# first check its number of elements
if (size > 0) :
# When array are not empty
i = 0
while (i < size) :
# Add element into tree
self.add_node(level_data[i])
i += 1
def main() :
obj = BinarySearchTree()
level_data = [5, 3, 9, 1, 4, 8, 11, 0, 2, 7, 12]
size = len(level_data)
obj.level_order_insert(level_data, size)
print("\nPerorder : ", end = "")
obj.preorder(obj.root)
print("\nInorder : ", end = "")
obj.inorder(obj.root)
print("\nPostorder : ", end = "")
obj.postorder(obj.root)
if __name__ == "__main__": main()
Output
Perorder : 5 3 1 0 2 4 9 8 7 11 12
Inorder : 0 1 2 3 4 5 7 8 9 11 12
Postorder : 0 2 1 4 3 7 8 12 11 9 5
# Ruby program
# Construct BST from level order traversal
# Binary Tree Node
class Node
# Define the accessor and reader of class Node
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
attr_accessor :root
# Class constructors
def initialize()
@root = nil
end
# insert element
def add_node(data)
# Create a new binary tree node
new_node = Node.new(data)
if (new_node != nil)
if (self.root == nil)
# When adds a first node in binary tree
self.root = new_node
else
find = self.root
# add new node to proper position
while (find != nil)
if (find.data >= data)
if (find.left == nil)
find.left = new_node
break
else
# visit left sub-tree
find = find.left
end
else
if (find.right == nil)
find.right = new_node
break
else
# visit right sub-tree
find = find.right
end
end
end
end
else
print("Memory Overflow")
end
end
def preorder(root)
if (root != nil)
print(" ", root.data)
self.preorder(root.left)
self.preorder(root.right)
end
end
def inorder(root)
if (root != nil)
self.inorder(root.left)
print(" ", root.data)
self.inorder(root.right)
end
end
def postorder(root)
if (root != nil)
self.postorder(root.left)
self.postorder(root.right)
print(" ", root.data)
end
end
# Construct BST using level order data
def level_order_insert(level_data, size)
# first check its number of elements
if (size > 0)
# When array are not empty
i = 0
while (i < size)
# Add element into tree
self.add_node(level_data[i])
i += 1
end
end
end
end
def main()
obj = BinarySearchTree.new()
level_data = [5, 3, 9, 1, 4, 8, 11, 0, 2, 7, 12]
size = level_data.length
obj.level_order_insert(level_data, size)
print("\nPerorder : ")
obj.preorder(obj.root)
print("\nInorder : ")
obj.inorder(obj.root)
print("\nPostorder : ")
obj.postorder(obj.root)
end
main()
Output
Perorder : 5 3 1 0 2 4 9 8 7 11 12
Inorder : 0 1 2 3 4 5 7 8 9 11 12
Postorder : 0 2 1 4 3 7 8 12 11 9 5
//Scala program
//Construct BST from level order traversal
//Binary Tree Node
class Node(var data: Int,
var left: Node,
var right: Node)
{
def this(data: Int)
{
this(data, null, null);
}
}
class BinarySearchTree(var root: Node)
{
//Class constructors
def this()
{
this(null);
}
//insert element
def add_node(data: Int): Unit = {
//Create a new binary tree node
var new_node: Node = new Node(data);
if (new_node != null)
{
if (this.root == null)
{
//When adds a first node in binary tree
this.root = new_node;
}
else
{
var find: Node = this.root;
//add new node to proper position
while (find != null)
{
if (find.data >= data)
{
if (find.left == null)
{
find.left = new_node;
return;
}
else
{
//visit left sub-tree
find = find.left;
}
}
else
{
if (find.right == null)
{
find.right = new_node;
return;
}
else
{
//visit right sub-tree
find = find.right;
}
}
}
}
}
else
{
print("Memory Overflow");
}
}
def preorder(root: Node): Unit = {
if (root != null)
{
print(" " + root.data);
preorder(root.left);
preorder(root.right);
}
}
def inorder(root: Node): Unit = {
if (root != null)
{
inorder(root.left);
print(" " + root.data);
inorder(root.right);
}
}
def postorder(root: Node): Unit = {
if (root != null)
{
postorder(root.left);
postorder(root.right);
print(" " + root.data);
}
}
//Construct BST using level order data
def level_order_insert(level_data: Array[Int], size: Int): Unit = {
//first check its number of elements
if (size > 0)
{
//When array are not empty
var i: Int = 0;
while (i < size)
{
//Add element into tree
add_node(level_data(i));
i += 1;
}
}
}
}
object Main
{
def main(args: Array[String]): Unit = {
var obj: BinarySearchTree = new BinarySearchTree();
var level_data: Array[Int] = Array(5, 3, 9, 1, 4, 8, 11, 0, 2, 7, 12);
var size: Int = level_data.length;
obj.level_order_insert(level_data, size);
print("\nPerorder : ");
obj.preorder(obj.root);
print("\nInorder : ");
obj.inorder(obj.root);
print("\nPostorder : ");
obj.postorder(obj.root);
}
}
Output
Perorder : 5 3 1 0 2 4 9 8 7 11 12
Inorder : 0 1 2 3 4 5 7 8 9 11 12
Postorder : 0 2 1 4 3 7 8 12 11 9 5
//Swift program
//Construct BST from level order traversal
//Binary Tree Node
class Node
{
var data: Int;
var left: Node? ;
var right: Node? ;
init(_ data: Int)
{
self.data = data;
self.left = nil;
self.right = nil;
}
}
class BinarySearchTree
{
var root: Node? ;
//Class constructors
init()
{
self.root = nil;
}
//insert element
func add_node(_ data: Int)
{
//Create a new binary tree node
let new_node: Node? = Node(data);
if (new_node != nil)
{
if (self.root == nil)
{
//When adds a first node in binary tree
self.root = new_node;
}
else
{
var find: Node? = self.root;
//add new node to proper position
while (find != nil)
{
if (find!.data >= data)
{
if (find!.left == nil)
{
find!.left = new_node;
break;
}
else
{
//visit left sub-tree
find = find!.left;
}
}
else
{
if (find!.right == nil)
{
find!.right = new_node;
break;
}
else
{
//visit right sub-tree
find = find!.right;
}
}
}
}
}
else
{
print("Memory Overflow", terminator: "");
}
}
func preorder(_ root: Node? )
{
if (root != nil)
{
print(" ", root!.data, terminator: "");
self.preorder(root!.left);
self.preorder(root!.right);
}
}
func inorder(_ root: Node? )
{
if (root != nil)
{
self.inorder(root!.left);
print(" ", root!.data, terminator: "");
self.inorder(root!.right);
}
}
func postorder(_ root: Node? )
{
if (root != nil)
{
self.postorder(root!.left);
self.postorder(root!.right);
print(" ", root!.data, terminator: "");
}
}
//Construct BST using level order data
func level_order_insert(_ level_data: [Int], _ size: Int)
{
//first check its number of elements
if (size > 0)
{
//When array are not empty
var i: Int = 0;
while (i < size)
{
//Add element into tree
self.add_node(level_data[i]);
i += 1;
}
}
}
}
func main()
{
let obj: BinarySearchTree = BinarySearchTree();
let level_data: [Int] = [5, 3, 9, 1, 4, 8, 11, 0, 2, 7, 12];
let size: Int = level_data.count;
obj.level_order_insert(level_data, size);
print("\nPerorder : ", terminator: "");
obj.preorder(obj.root);
print("\nInorder : ", terminator: "");
obj.inorder(obj.root);
print("\nPostorder : ", terminator: "");
obj.postorder(obj.root);
}
main();
Output
Perorder : 5 3 1 0 2 4 9 8 7 11 12
Inorder : 0 1 2 3 4 5 7 8 9 11 12
Postorder : 0 2 1 4 3 7 8 12 11 9 5
//Node Js program
//Construct BST from level order traversal
//Binary Tree Node
class Node
{
constructor(data)
{
this.data = data;
this.left = null;
this.right = null;
}
}
class BinarySearchTree
{
//Class constructors
constructor()
{
this.root = null;
}
//insert element
add_node(data)
{
//Create a new binary tree node
var new_node = new Node(data);
if (new_node != null)
{
if (this.root == null)
{
//When adds a first node in binary tree
this.root = new_node;
}
else
{
var find = this.root;
//add new node to proper position
while (find != null)
{
if (find.data >= data)
{
if (find.left == null)
{
find.left = new_node;
break;
}
else
{
//visit left sub-tree
find = find.left;
}
}
else
{
if (find.right == null)
{
find.right = new_node;
break;
}
else
{
//visit right sub-tree
find = find.right;
}
}
}
}
}
else
{
process.stdout.write("Memory Overflow");
}
}
preorder(root)
{
if (root != null)
{
process.stdout.write(" " + root.data);
this.preorder(root.left);
this.preorder(root.right);
}
}
inorder(root)
{
if (root != null)
{
this.inorder(root.left);
process.stdout.write(" " + root.data);
this.inorder(root.right);
}
}
postorder(root)
{
if (root != null)
{
this.postorder(root.left);
this.postorder(root.right);
process.stdout.write(" " + root.data);
}
}
//Construct BST using level order data
level_order_insert(level_data, size)
{
//first check its number of elements
if (size > 0)
{
//When array are not empty
var i = 0;
while (i < size)
{
//Add element into tree
this.add_node(level_data[i]);
++i;
}
}
}
}
function main()
{
var obj = new BinarySearchTree();
var level_data = [5, 3, 9, 1, 4, 8, 11, 0, 2, 7, 12];
var size = level_data.length;
obj.level_order_insert(level_data, size);
process.stdout.write("\nPerorder : ");
obj.preorder(obj.root);
process.stdout.write("\nInorder : ");
obj.inorder(obj.root);
process.stdout.write("\nPostorder : ");
obj.postorder(obj.root);
}
main();
Output
Perorder : 5 3 1 0 2 4 9 8 7 11 12
Inorder : 0 1 2 3 4 5 7 8 9 11 12
Postorder : 0 2 1 4 3 7 8 12 11 9 5
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