Construct a tree from Inorder and Level order
Constructing a tree from its Inorder and Level order traversals means building a binary tree with the given Inorder and Level order traversal sequences.
Inorder traversal of a binary tree is defined as the traversal sequence in which the left subtree is visited first, then the root node, and then the right subtree.
Level order traversal of a binary tree is defined as the traversal sequence in which the nodes are visited level by level, from left to right.
Constructing a tree from these two traversals involves the following steps:
- The first element in the Level order traversal is the root node of the binary tree.
- Find the position of the root node in the Inorder traversal sequence. All the elements before this position in Inorder traversal belong to the left subtree, and all the elements after this position belong to the right subtree.
- Recursively repeat steps 1 and 2 for the left and right subtrees until all the nodes are constructed.
Overall, constructing a tree from Inorder and Level order requires a combination of the information provided by both traversals to build the tree structure.
Program List
/*
C Program
+ Construct a tree from Inorder and Level order
*/
#include <stdio.h>
#include <stdlib.h>
//structure of Binary Tree node
struct Node {
int data;
struct Node *left, *right;
};
struct Node *insert(int data) {
//create dynamic memory to new binary tree node
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
} else {
printf("Memory Overflow\n");
exit(0); //Terminate program execution
}
//return reference
return new_node;
}
int getIndex(int node[], int size, int value) {
if (size <= 1) return -1;
int index = -1;
for (int i = 0; i < size; ++i) {
if (node[i] == value) {
index = i;
break;
}
}
return index;
}
//Display tree element inorder form
void inorderData(struct Node *node) {
if (node != NULL) {
inorderData(node->left);
//Print node value
printf("%3d", node->data);
inorderData(node->right);
}
}
//Display tree element preorder form
void preOrderData(struct Node *node) {
if (node != NULL) {
//Print node value
printf("%3d", node->data);
preOrderData(node->left);
preOrderData(node->right);
}
}
//Display tree element postorder form
void postOrderData(struct Node *node) {
if (node != NULL) {
postOrderData(node->left);
postOrderData(node->right);
//Print node value
printf("%3d", node->data);
}
}
struct Node *construct(int inorder[], int levelorder[], int size) {
struct Node *root = NULL, *store = NULL;
int head = -1, temp = -1, need = 0;
for (int i = 0; i < size; ++i) {
if (i == 0) {
root = insert(levelorder[i]);
head = getIndex(inorder, size, levelorder[i]);
} else {
store = root;
temp = getIndex(inorder, size, levelorder[i]);
need = head;
//That is similar to binary search tree find the position of newly inserted node
while (store != NULL) {
if (temp < head) {
if (store->left == NULL) {
//when next left child node is empty, then add new element
store->left = insert(levelorder[i]);
break;
} else {
store = store->left;
head = getIndex(inorder, size, store->data);
}
} else {
if (store->right == NULL) {
//when next right child node is empty, then add new element
store->right = insert(levelorder[i]);
break;
} else {
store = store->right;
head = getIndex(inorder, size, store->data);
}
}
}
head = need;
}
}
return root;
}
int main() {
/*
1
/ \
2 6
/ \ \
3 5 7
/ /
8 9
*/
int inorder[] = {
8,
3,
2,
5,
1,
6,
9,
7
};
int levelorder[] = {
1,
2,
6,
3,
5,
7,
8,
9
};
//Assuming that given Inorder and level order are equal size
int size = sizeof(inorder) / sizeof(inorder[0]);
struct Node *root = construct(inorder, levelorder, size);
printf("\nInorder Data : ");
inorderData(root);
printf("\nPreorder Data : ");
preOrderData(root);
printf("\nPostorder Data : ");
postOrderData(root);
return 0;
}
Output
Inorder Data : 8 3 2 5 1 6 9 7
Preorder Data : 1 2 3 8 5 6 7 9
Postorder Data : 8 3 5 2 9 7 6 1/*
C++ Program
Construct a tree from Inorder and Level order
*/
#include<iostream>
using namespace std;
class Node {
public:
int data;
Node *left, *right;
Node(int value) {
this->data = value;
this->left = this->right = NULL;
}
};
class BinaryTree {
public:
Node *root;
BinaryTree() {
this->root = NULL;
}
void in_order(Node *node) {
if (node != NULL) {
this->in_order(node->left);
cout <<" " << node->data;
this->in_order(node->right);
}
}
void pre_order(Node *node) {
if (node != NULL) {
cout << " " << node->data;
this->pre_order(node->left);
this->pre_order(node->right);
}
}
void post_order(Node *node) {
if (node != NULL) {
this->post_order(node->left);
this->post_order(node->right);
cout << " " << node->data;
}
}
int getIndex(int node[], int size, int value) {
if (size <= 1) {
return -1;
}
int index = -1;
int i = 0;
while (i < size) {
if (node[i] == value) {
index = i;
break;
}
i++;
}
return index;
}
Node *construct(int inorder[], int levelorder[], int size) {
Node *head = NULL, *store = NULL;
int location = -1, temp = -1, need = 0;
int i = 0;
while (i < size) {
if (i == 0) {
head = new Node(levelorder[i]);
location = this->getIndex(inorder, size, levelorder[i]);
} else {
store = head;
temp = this->getIndex(inorder, size, levelorder[i]);
need = location;
while (store != NULL) {
if (temp < location) {
if (store->left == NULL) {
store->left = new Node(levelorder[i]);
break;
} else {
store = store->left;
location = this->getIndex(inorder, size, store->data);
}
} else {
if (store->right == NULL) {
store->right = new Node(levelorder[i]);
break;
} else {
store = store->right;
location = this->getIndex(inorder, size, store->data);
}
}
}
location = need;
}
i++;
}
return head;
}
};
int main() {
BinaryTree obj ;
int inorder[] = {
8,
3,
2,
5,
1,
6,
9,
7
};
int levelorder[] = {
1,
2,
6,
3,
5,
7,
8,
9
};
//Assume levelorder and inorder array are same size
int size = sizeof(levelorder)/sizeof(levelorder[0]);
obj.root = obj.construct(inorder, levelorder,size);
cout << "\nIn-order Data : ";
obj.in_order(obj.root);
cout << "\nPre-order Data : ";
obj.pre_order(obj.root);
cout << "\nPost-order Data : ";
obj.post_order(obj.root);
return 0;
}
Output
In-order Data : 8 3 2 5 1 6 9 7
Pre-order Data : 1 2 3 8 5 6 7 9
Post-order Data : 8 3 5 2 9 7 6 1/*
Java Program
Construct a tree from Inorder and Level order
*/
//Class of Binary Tree node
class Node {
public int data;
public Node left, right;
//Make a tree node
public Node(int data) {
//Assign field values
this.data = data;
left = right = null;
}
}
public class BinaryTree {
public Node root;
public BinaryTree() {
//Set initial initial values
root = null;
}
//Display tree element inorder form
public void in_order(Node node) {
if (node != null) {
in_order(node.left);
//Print node value
System.out.print(" " + node.data);
in_order(node.right);
}
}
//Display tree element preorder form
public void pre_order(Node node) {
if (node != null) {
//Print node value
System.out.print(" " + node.data);
pre_order(node.left);
pre_order(node.right);
}
}
//Display tree element preorder form
public void post_order(Node node) {
if (node != null) {
post_order(node.left);
post_order(node.right);
//Print node value
System.out.print(" " + node.data);
}
}
public int getIndex(int[] node, int size, int value) {
if (size <= 1) {
return -1;
}
int index = -1;
int i = 0;
while (i < size) {
if (node[i] == value) {
index = i;
break;
}
i++;
}
return index;
}
public Node construct(int[] inorder, int[] levelorder) {
if (inorder.length != levelorder.length) {
return null;
}
Node head = null, store = null;
int location = -1, temp = -1, need = 0;
int size = inorder.length, i = 0;
while (i < size) {
if (i == 0) {
head = new Node(levelorder[i]);
location = getIndex(inorder, size, levelorder[i]);
} else {
store = head;
temp = getIndex(inorder, size, levelorder[i]);
need = location;
//That is similar to binary search tree find the position of newly new Nodeed node
while (store != null) {
if (temp < location) {
if (store.left == null) {
//when next left child node is empty, then add new element
store.left = new Node(levelorder[i]);
break;
} else {
store = store.left;
location = getIndex(inorder, size, store.data);
}
} else {
if (store.right == null) {
//when next right child node is empty, then add new element
store.right = new Node(levelorder[i]);
break;
} else {
store = store.right;
location = getIndex(inorder, size, store.data);
}
}
}
location = need;
}
i++;
}
return head;
}
public static void main(String[] args) {
//Make object of Binary Tree
BinaryTree obj = new BinaryTree();
/*
1
/ \
2 6
/ \ \
3 5 7
/ /
8 9
*/
int []inorder = {8, 3, 2, 5, 1, 6, 9 , 7};
int []levelorder = {1, 2, 6, 3, 5, 7, 8, 9};
obj.root = obj.construct(inorder, levelorder);
System.out.print("\nIn-order Data : ");
obj.in_order(obj.root);
System.out.print("\nPre-order Data : ");
obj.pre_order(obj.root);
System.out.print("\nPost-order Data : ");
obj.post_order(obj.root);
}
}
Output
In-order Data : 8 3 2 5 1 6 9 7
Pre-order Data : 1 2 3 8 5 6 7 9
Post-order Data : 8 3 5 2 9 7 6 1/*
C# Program
Construct a tree from Inorder and Level order
*/
using System;
//Class of Binary Tree node
public class Node {
public int data;
public Node left, right;
//Make a tree node
public Node(int data) {
//Assign field values
this.data = data;
left = right = null;
}
}
public class BinaryTree {
public Node root;
public BinaryTree() {
//Set initial initial values
root = null;
}
//Display tree element inorder form
public void in_order(Node node) {
if (node != null) {
in_order(node.left);
//Print node value
Console.Write(" " + node.data);
in_order(node.right);
}
}
//Display tree element preorder form
public void pre_order(Node node) {
if (node != null) {
//Print node value
Console.Write(" " + node.data);
pre_order(node.left);
pre_order(node.right);
}
}
//Display tree element preorder form
public void post_order(Node node) {
if (node != null) {
post_order(node.left);
post_order(node.right);
//Print node value
Console.Write(" " + node.data);
}
}
public int getIndex(int[] node, int size, int value) {
if (size <= 1) {
return -1;
}
int index = -1;
int i = 0;
while (i < size) {
if (node[i] == value) {
index = i;
break;
}
i++;
}
return index;
}
public Node construct(int[] inorder, int[] levelorder) {
if (inorder.Length != levelorder.Length) {
return null;
}
Node head = null, store = null;
int location = -1, temp = -1, need = 0;
int size = inorder.Length, i = 0;
while (i < size) {
if (i == 0) {
head = new Node(levelorder[i]);
location = getIndex(inorder, size, levelorder[i]);
} else {
store = head;
temp = getIndex(inorder, size, levelorder[i]);
need = location;
//That is similar to binary search tree find the position of newly new Nodeed node
while (store != null) {
if (temp < location) {
if (store.left == null) {
//when next left child node is empty, then add new element
store.left = new Node(levelorder[i]);
break;
} else {
store = store.left;
location = getIndex(inorder, size, store.data);
}
} else {
if (store.right == null) {
//when next right child node is empty, then add new element
store.right = new Node(levelorder[i]);
break;
} else {
store = store.right;
location = getIndex(inorder, size, store.data);
}
}
}
location = need;
}
i++;
}
return head;
}
public static void Main(String[] args) {
//Make object of Binary Tree
BinaryTree obj = new BinaryTree();
/*
1
/ \
2 6
/ \ \
3 5 7
/ /
8 9
*/
int []inorder = {8, 3, 2, 5, 1, 6, 9 , 7};
int []levelorder = {1, 2, 6, 3, 5, 7, 8, 9};
obj.root = obj.construct(inorder, levelorder);
Console.Write("\nIn-order Data : ");
obj.in_order(obj.root);
Console.Write("\nPre-order Data : ");
obj.pre_order(obj.root);
Console.Write("\nPost-order Data : ");
obj.post_order(obj.root);
}
}
Output
In-order Data : 8 3 2 5 1 6 9 7
Pre-order Data : 1 2 3 8 5 6 7 9
Post-order Data : 8 3 5 2 9 7 6 1# Python Program
# Construct a tree from Inorder and Level order
class Node :
def __init__(self, value) :
self.data = value
self.left = None
self.right = None
class BinaryTree :
def __init__(self) :
self.root = None
def in_order(self, node) :
if (node != None) :
self.in_order(node.left)
print(node.data, end=" ")
self.in_order(node.right)
def pre_order(self, node) :
if (node != None) :
print(node.data, end=" ")
self.pre_order(node.left)
self.pre_order(node.right)
def post_order(self, node) :
if (node != None) :
self.post_order(node.left)
self.post_order(node.right)
print(node.data, end=" ")
def getIndex(self, node, size, value) :
if (size <= 1) :
return -1
index = -1
i = 0
while (i < size) :
if (node[i] == value) :
index = i
break
i += 1
return index
def construct(self, inorder, levelorder) :
if (len(inorder) != len(levelorder)) :
return None
head = None
store = None
location = -1
temp = -1
need = 0
size = len(inorder)
i = 0
while (i < size) :
if (i == 0) :
head = Node(levelorder[i])
location = self.getIndex(inorder, size, levelorder[i])
else :
store = head
temp = self.getIndex(inorder, size, levelorder[i])
need = location
while (store != None) :
if (temp < location) :
if (store.left == None) :
store.left = Node(levelorder[i])
break
else :
store = store.left
location = self.getIndex(inorder, size, store.data)
else :
if (store.right == None) :
store.right = Node(levelorder[i])
break
else :
store = store.right
location = self.getIndex(inorder, size, store.data)
location = need
i += 1
return head
def main() :
obj = BinaryTree()
inorder = [8, 3, 2, 5, 1, 6, 9, 7]
levelorder = [1, 2, 6, 3, 5, 7, 8, 9]
obj.root = obj.construct(inorder, levelorder)
print("\nIn-order Data : ")
obj.in_order(obj.root)
print("\nPre-order Data : ")
obj.pre_order(obj.root)
print("\nPost-order Data : ")
obj.post_order(obj.root)
if __name__ == "__main__":
main()
Output
In-order Data :
8 3 2 5 1 6 9 7
Pre-order Data :
1 2 3 8 5 6 7 9
Post-order Data :
8 3 5 2 9 7 6 1 # Ruby Program
# Construct a tree from Inorder and Level order
class Node
attr_reader :data, :left, :right
attr_accessor :data, :left, :right
def initialize(value)
@data = value
@left = nil
@right = nil
end
end
class BinaryTree
attr_reader :root
attr_accessor :root
def initialize()
@root = nil
end
def in_order(node)
if (node != nil)
self.in_order(node.left)
print(" ", node.data)
self.in_order(node.right)
end
end
def pre_order(node)
if (node != nil)
print(" ", node.data)
self.pre_order(node.left)
self.pre_order(node.right)
end
end
def post_order(node)
if (node != nil)
self.post_order(node.left)
self.post_order(node.right)
print(" ", node.data)
end
end
def getlocation(node, size, value)
if (size <= 1)
return -1
end
location = -1
i = 0
while (i < size)
if (node[i] == value)
location = i
break
end
i += 1
end
return location
end
def construct(inorder, levelorder)
if (inorder.length != levelorder.length)
return nil
end
head = nil
store = nil
location = -1
temp = -1
need = 0
size = inorder.length
i = 0
while (i < size)
if (i == 0)
head = Node.new(levelorder[i])
location = self.getlocation(inorder, size, levelorder[i])
else
store = head
temp = self.getlocation(inorder, size, levelorder[i])
need = location
while (store != nil)
if (temp < location)
if (store.left == nil)
store.left = Node.new(levelorder[i])
break
else
store = store.left
location = self.getlocation(inorder, size, store.data)
end
else
if (store.right == nil)
store.right = Node.new(levelorder[i])
break
else
store = store.right
location = self.getlocation(inorder, size, store.data)
end
end
end
location = need
end
i += 1
end
return head
end
end
def main()
obj = BinaryTree.new()
inorder = [8, 3, 2, 5, 1, 6, 9, 7]
levelorder = [1, 2, 6, 3, 5, 7, 8, 9]
obj.root = obj.construct(inorder, levelorder)
print("\nIn-order Data :")
obj.in_order(obj.root)
print("\nPre-order Data :")
obj.pre_order(obj.root)
print("\nPost-order Data :")
obj.post_order(obj.root)
end
main()
Output
In-order Data : 8 3 2 5 1 6 9 7
Pre-order Data : 1 2 3 8 5 6 7 9
Post-order Data : 8 3 5 2 9 7 6 1<?php
/*
Php Program
Construct a tree from Inorder and Level order
*/
class Node {
public $data;
public $left;
public $right;
function __construct($value) {
$this->data = $value;
$this->left = null;
$this->right = null;
}
}
class BinaryTree {
public $root;
function __construct() {
$this->root = null;
}
public function in_order($node) {
if ($node != null) {
$this->in_order($node->left);
echo " ". $node->data;
$this->in_order($node->right);
}
}
public function pre_order($node) {
if ($node != null) {
echo " ". $node->data;
$this->pre_order($node->left);
$this->pre_order($node->right);
}
}
public function post_order($node) {
if ($node != null) {
$this->post_order($node->left);
$this->post_order($node->right);
echo " ". $node->data;
}
}
public function getIndex(&$node, $size, $value) {
if ($size <= 1) {
return -1;
}
$index = -1;
$i = 0;
while ($i < $size) {
if ($node[$i] == $value) {
$index = $i;
break;
}
$i++;
}
return $index;
}
public function construct($inorder, $levelorder) {
if (count($inorder) != count($levelorder)) {
return null;
}
$head = null;
$store = null;
$location = -1;
$temp = -1;
$need = 0;
$size = count($inorder);
$i = 0;
while ($i < $size) {
if ($i == 0) {
$head = new Node($levelorder[$i]);
$location = $this->getIndex($inorder, $size, $levelorder[$i]);
} else {
$store = $head;
$temp = $this->getIndex($inorder, $size, $levelorder[$i]);
$need = $location;
while ($store != null) {
if ($temp < $location) {
if ($store->left == null) {
$store->left = new Node($levelorder[$i]);
break;
} else {
$store = $store->left;
$location = $this->getIndex($inorder, $size, $store->data);
}
} else {
if ($store->right == null) {
$store->right = new Node($levelorder[$i]);
break;
} else {
$store = $store->right;
$location = $this->getIndex($inorder, $size, $store->data);
}
}
}
$location = $need;
}
$i++;
}
return $head;
}
}
function main() {
$obj = new BinaryTree();
$inorder = array(8, 3, 2, 5, 1, 6, 9, 7);
$levelorder = array(1, 2, 6, 3, 5, 7, 8, 9);
$obj->root = $obj->construct($inorder, $levelorder);
echo ("\nIn-order Data : ");
$obj->in_order($obj->root);
echo ("\nPre-order Data : ");
$obj->pre_order($obj->root);
echo ("\nPost-order Data : ");
$obj->post_order($obj->root);
}
main();
Output
In-order Data : 8 3 2 5 1 6 9 7
Pre-order Data : 1 2 3 8 5 6 7 9
Post-order Data : 8 3 5 2 9 7 6 1/*
Node JS Program
Construct a tree from Inorder and Level order
*/
class Node {
constructor(value) {
this.data = value;
this.left = null;
this.right = null;
}
}
class BinaryTree {
constructor() {
this.root = null;
}
in_order(node) {
if (node != null) {
this.in_order(node.left);
process.stdout.write(" " + node.data);
this.in_order(node.right);
}
}
pre_order(node) {
if (node != null) {
process.stdout.write(" " + node.data);
this.pre_order(node.left);
this.pre_order(node.right);
}
}
post_order(node) {
if (node != null) {
this.post_order(node.left);
this.post_order(node.right);
process.stdout.write(" " + node.data);
}
}
getIndex(node, size, value) {
if (size <= 1) {
return -1;
}
var index = -1;
var i = 0;
while (i < size) {
if (node[i] == value) {
index = i;
break;;
}
i++;
}
return index;
}
construct(inorder, levelorder) {
if (inorder.length != levelorder.length) {
return null;
}
var head = null;
var store = null;
var location = -1;
var temp = -1;
var need = 0;
var size = inorder.length;
var i = 0;
while (i < size) {
if (i == 0) {
head = new Node(levelorder[i]);
location = this.getIndex(inorder, size, levelorder[i]);
} else {
store = head;
temp = this.getIndex(inorder, size, levelorder[i]);
need = location;
while (store != null) {
if (temp < location) {
if (store.left == null) {
store.left = new Node(levelorder[i]);
break;;
} else {
store = store.left;
location = this.getIndex(inorder, size, store.data);
}
} else {
if (store.right == null) {
store.right = new Node(levelorder[i]);
break;;
} else {
store = store.right;
location = this.getIndex(inorder, size, store.data);
}
}
}
location = need;
}
i++;
}
return head;
}
}
function main() {
var obj = new BinaryTree();
var inorder = [8, 3, 2, 5, 1, 6, 9, 7];
var levelorder = [1, 2, 6, 3, 5, 7, 8, 9];
obj.root = obj.construct(inorder, levelorder);
process.stdout.write("\nIn-order Data : ");
obj.in_order(obj.root);
process.stdout.write("\nPre-order Data : ");
obj.pre_order(obj.root);
process.stdout.write("\nPost-order Data : ");
obj.post_order(obj.root);
}
main();
Output
In-order Data : 8 3 2 5 1 6 9 7
Pre-order Data : 1 2 3 8 5 6 7 9
Post-order Data : 8 3 5 2 9 7 6 1/*
Swift 4 Program
Construct a tree from Inorder and Level order
*/
class Node {
var data: Int;
var left: Node? ;
var right: Node? ;
init(_ value: Int) {
self.data = value;
self.left = nil;
self.right = nil;
}
}
class BinaryTree {
var root: Node? ;
init() {
self.root = nil;
}
func in_order(_ node: Node? ) {
if (node != nil) {
self.in_order(node!.left);
print(node!.data, terminator:" ");
self.in_order(node!.right);
}
}
func pre_order(_ node: Node? ) {
if (node != nil) {
print(node!.data, terminator:" ");
self.pre_order(node!.left);
self.pre_order(node!.right);
}
}
func post_order(_ node: Node? ) {
if (node != nil) {
self.post_order(node!.left);
self.post_order(node!.right);
print(node!.data, terminator:" ");
}
}
func getIndex(_ node: inout [Int] , _ size : Int, _ value: Int) -> Int {
if (size <= 1) {
return -1;
}
var index: Int = -1;
var i: Int = 0;
while (i < size) {
if (node[i] == value) {
index = i;
break;
}
i += 1;
}
return index;
}
func construct(_ inorder: inout [Int] , _ levelorder : [Int] )->Node? {
if (inorder.count != levelorder.count) {
return nil;
}
var head: Node? = nil;
var store: Node? = nil;
var location: Int = -1;
var temp = -1;
var need = 0;
let size: Int = inorder.count;
var i = 0;
while (i < size) {
if (i == 0) {
head = Node(levelorder[i]);
location = self.getIndex(&inorder, size, levelorder[i]);
} else {
store = head;
temp = self.getIndex(&inorder, size, levelorder[i]);
need = location;
while (store != nil) {
if (temp < location) {
if (store!.left == nil) {
store!.left = Node(levelorder[i]);
break;
} else {
store = store!.left;
location = self.getIndex(&inorder, size, store!.data);
}
} else {
if (store!.right == nil) {
store!.right = Node(levelorder[i]);
break;
} else {
store = store!.right;
location = self.getIndex(&inorder, size, store!.data);
}
}
}
location = need;
}
i += 1;
}
return head;
}
}
func main() {
let obj: BinaryTree = BinaryTree();
var inorder: [Int] = [8, 3, 2, 5, 1, 6, 9, 7];
let levelorder: [Int] = [1, 2, 6, 3, 5, 7, 8, 9];
obj.root = obj.construct(&inorder, levelorder);
print("\nIn-order Data : ");
obj.in_order(obj.root);
print("\nPre-order Data : ");
obj.pre_order(obj.root);
print("\nPost-order Data : ");
obj.post_order(obj.root);
}
main();
Output
In-order Data :
8 3 2 5 1 6 9 7
Pre-order Data :
1 2 3 8 5 6 7 9
Post-order Data :
8 3 5 2 9 7 6 1
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