Construct Tree from given Inorder and Preorder Traversals
Constructing a tree from its inorder and preorder traversals is a common problem in computer science, particularly in the field of data structures and algorithms. The problem involves taking two sequences of values representing the order in which a binary tree is traversed in inorder and preorder, and using them to reconstruct the original binary tree.
To understand this problem, it is important to understand what is meant by inorder and preorder traversal. Inorder traversal of a binary tree involves visiting the left subtree, then the root, and then the right subtree in that order. Preorder traversal, on the other hand, involves visiting the root, then the left subtree, and then the right subtree in that order. These two traversals give different orders in which the nodes of a binary tree can be visited.
Code Solution
/*
C Program
Construct Tree from given Inorder and Preorder traversals
*/
#include <stdio.h>
#include <stdlib.h>
//Binary Tree node
struct Node
{
int data;
struct Node *left, *right;
};
//This is creating a binary tree node and return new node
struct Node *get_node(int data)
{
// Create dynamic 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;
new_node->right = NULL;
}
else
{
//This is indicates, segmentation fault or memory overflow problem
printf("Memory Overflow\n");
}
//return new node
return new_node;
}
//Display inorder elements
void print_inorder(struct Node *node)
{
if (node != NULL)
{
print_inorder(node->left);
//Print node value
printf(" %d", node->data);
print_inorder(node->right);
}
}
//Display pre order elements
void print_preorder(struct Node *node)
{
if (node != NULL)
{
//Print node value
printf(" %d", node->data);
print_preorder(node->left);
print_preorder(node->right);
}
}
//Display postorder elements
void print_postorder(struct Node *node)
{
if (node != NULL)
{
print_postorder(node->left);
print_postorder(node->right);
//Print node value
printf(" %d", node->data);
}
}
//Constructing a binary tree from given inorder and preorder
struct Node *construct_tree(int inorder[], int preorder[], int first, int last, int *location, int size)
{
if ( *location > size || first > last)
{
return NULL;
}
struct Node *node = NULL;
for (int i = first; i <= last && node == NULL; ++i)
{
//Find node
if (preorder[ *location] == inorder[i])
{
// Create node
node = get_node(inorder[i]);
// next element of preorder
*location = *location + 1;
//Recursively constructing left and right subtree
node->left = construct_tree(inorder, preorder, first, i - 1, location, size);
node->right = construct_tree(inorder, preorder, i + 1, last, location, size);
}
}
return node;
}
//handles the request of construct binary tree
struct Node *make_tree(int inorder[], int preorder[], int n1, int n2)
{
if (n1 != n2)
{
//Invalid sequence
return NULL;
}
else
{
int location = 0;
return construct_tree(inorder, preorder, 0, n1 - 1, & location, n2 - 1);
}
}
//Handles the request of display the element of tree
void print_tree(struct Node *root)
{
printf("\n Preorder : ");
print_preorder(root);
printf("\n Inorder : ");
print_inorder(root);
printf("\n Postorder : ");
print_postorder(root);
printf("\n");
}
int main()
{
/*
----------------------------
8
/ \
2 7
/ \ / \
6 9 4 5
/ \ / \
1 3 23 90
-------------------------------
Inorder sequence: 1 6 3 2 9 8 4 7 23 5 90
Preorder sequence: 8 2 6 1 3 9 7 4 5 23 90
*/
int inorder1[] = {
1 , 6 , 3 , 2 , 9 , 8 , 4 , 7 , 23 , 5 , 90
};
int preorder1[] = {
8 , 2 , 6 , 1 , 3 , 9 , 7 , 4 , 5 , 23 , 90
};
// Get the size of arrays
int n1 = sizeof(inorder1) / sizeof(inorder1[0]);
int n2 = sizeof(preorder1) / sizeof(preorder1[0]);
struct Node *root1 = make_tree(inorder1, preorder1, n1, n2);
print_tree(root1);
/*
--------------
1
/ \
2 3
/ \ / \
4 5 9 7
----------------
*/
int inorder2[] = {
4 , 2 , 5 , 1 , 9 , 3 , 7
};
int preorder2[] = {
1 , 2 , 4 , 5 , 3 , 9 , 7
};
// Get the size of arrays
n1 = sizeof(inorder2) / sizeof(inorder2[0]);
n2 = sizeof(preorder2) / sizeof(preorder2[0]);
struct Node *root2 = make_tree(inorder2, preorder2, n1, n2);
print_tree(root2);
return 0;
}Output
Preorder : 8 2 6 1 3 9 7 4 5 23 90
Inorder : 1 6 3 2 9 8 4 7 23 5 90
Postorder : 1 3 6 9 2 4 23 90 5 7 8
Preorder : 1 2 4 5 3 9 7
Inorder : 4 2 5 1 9 3 7
Postorder : 4 5 2 9 7 3 1/*
Java Program
Construct Tree from given Inorder and Preorder traversals
*/
// Binary Tree node
class Node
{
public int data;
public Node left;
public Node right;
public Node(int data)
{
// Set node value
this.data = data;
this.left = null;
this.right = null;
}
}
//Define Binary Tree
public class BinaryTree
{
public Node root;
public int location;
public BinaryTree()
{
//Set root of tree
this.root = null;
this.location = 0;
}
//Display inorder elements
public void print_inorder(Node node)
{
if (node != null)
{
print_inorder(node.left);
//Print node value
System.out.print(" " + node.data);
print_inorder(node.right);
}
}
//Display pre order elements
public void print_preorder(Node node)
{
if (node != null)
{
//Print node value
System.out.print(" " + node.data);
print_preorder(node.left);
print_preorder(node.right);
}
}
//Display postorder elements
public void print_postorder(Node node)
{
if (node != null)
{
print_postorder(node.left);
print_postorder(node.right);
//Print node value
System.out.print(" " + node.data);
}
}
//Constructing a binary tree from given inorder and preorder
public Node construct_tree(int[] inorder, int[] preorder, int first, int last, int size)
{
if (this.location > size || first > last)
{
return null;
}
Node node = null;
for (int i = first; i <= last && node == null; ++i)
{
//Find node
if (preorder[location] == inorder[i])
{
// Create node
node = new Node(inorder[i]);
// next element of preorder
this.location = this.location + 1;
//Recursively constructing left and right subtree
node.left = construct_tree(inorder, preorder, first, i - 1, size);
node.right = construct_tree(inorder, preorder, i + 1, last, size);
}
}
return node;
}
//handles the request of construct binary tree
public void make_tree(int[] inorder, int[] preorder, int n1, int n2)
{
if (n1 != n2)
{
//Invalid sequence
this.root = null;
}
else
{
this.location = 0;
this.root = construct_tree(inorder, preorder, 0, n1 - 1, n2 - 1);
}
}
//Handles the request of display the element of tree
public void print_tree()
{
if(this.root==null)
{
System.out.print("\n Empty Tree\n");
return;
}
System.out.print("\n Preorder : ");
print_preorder(root);
System.out.print("\n Inorder : ");
print_inorder(root);
System.out.print("\n Postorder : ");
print_postorder(root);
System.out.print("\n");
}
public static void main(String[] args)
{
//Create tree object
BinaryTree tree1 = new BinaryTree();
BinaryTree tree2 = new BinaryTree();
/*
----------------------------
8
/ \
2 7
/ \ / \
6 9 4 5
/ \ / \
1 3 23 90
-------------------------------
Inorder sequence: 1 6 3 2 9 8 4 7 23 5 90
Preorder sequence: 8 2 6 1 3 9 7 4 5 23 90
*/
int[] inorder1 = {
1 , 6 , 3 , 2 , 9 , 8 , 4 , 7 , 23 , 5 , 90
};
int[] preorder1 = {
8 , 2 , 6 , 1 , 3 , 9 , 7 , 4 , 5 , 23 , 90
};
// Get the size of arrays
int n1 = inorder1.length;
int n2 = preorder1.length;
tree1.make_tree(inorder1, preorder1, n1, n2);
tree1.print_tree();
/*
--------------
1
/ \
2 3
/ \ / \
4 5 9 7
----------------
*/
int []inorder2 = {
4 , 2 , 5 , 1 , 9 , 3 , 7
};
int []preorder2 = {
1 , 2 , 4 , 5 , 3 , 9 , 7
};
// Get the size of arrays
n1 = inorder2.length;
n2 = preorder2.length;
tree2.make_tree(inorder2, preorder2, n1, n2);
tree2.print_tree();
}
}Output
Preorder : 8 2 6 1 3 9 7 4 5 23 90
Inorder : 1 6 3 2 9 8 4 7 23 5 90
Postorder : 1 3 6 9 2 4 23 90 5 7 8
Preorder : 1 2 4 5 3 9 7
Inorder : 4 2 5 1 9 3 7
Postorder : 4 5 2 9 7 3 1// Include header file
#include <iostream>
using namespace std;
// C++ Program
// Construct Tree from given Inorder and Preorder traversals
// Binary Tree node
class Node
{
public: int data;
Node *left;
Node *right;
Node(int data)
{
// Set node value
this->data = data;
this->left = NULL;
this->right = NULL;
}
};
// Define Binary Tree
class BinaryTree
{
public: Node *root;
int location;
BinaryTree()
{
// Set root of tree
this->root = NULL;
this->location = 0;
}
// Display inorder elements
void print_inorder(Node *node)
{
if (node != NULL)
{
this->print_inorder(node->left);
// Print node value
cout << " " << node->data;
this->print_inorder(node->right);
}
}
// Display pre order elements
void print_preorder(Node *node)
{
if (node != NULL)
{
// Print node value
cout << " " << node->data;
this->print_preorder(node->left);
this->print_preorder(node->right);
}
}
// Display postorder elements
void print_postorder(Node *node)
{
if (node != NULL)
{
this->print_postorder(node->left);
this->print_postorder(node->right);
// Print node value
cout << " " << node->data;
}
}
// Constructing a binary tree from given inorder and preorder
Node *construct_tree(int inorder[], int preorder[], int first, int last, int size)
{
if (this->location > size || first > last)
{
return NULL;
}
Node *node = NULL;
for (int i = first; i <= last && node == NULL; ++i)
{
// Find node
if (preorder[this->location] == inorder[i])
{
// Create node
node = new Node(inorder[i]);
// next element of preorder
this->location = this->location + 1;
// Recursively constructing left and right subtree
node->left = this->construct_tree(inorder, preorder, first, i - 1, size);
node->right = this->construct_tree(inorder, preorder, i + 1, last, size);
}
}
return node;
}
// handles the request of construct binary tree
void make_tree(int inorder[], int preorder[], int n1, int n2)
{
if (n1 != n2)
{
// Invalid sequence
this->root = NULL;
}
else
{
this->location = 0;
this->root = this->construct_tree(inorder, preorder, 0, n1 - 1, n2 - 1);
}
}
// Handles the request of display the element of tree
void print_tree()
{
if (this->root == NULL)
{
cout << "\n Empty Tree\n";
return;
}
cout << "\n Preorder : ";
this->print_preorder(this->root);
cout << "\n Inorder : ";
this->print_inorder(this->root);
cout << "\n Postorder : ";
this->print_postorder(this->root);
cout << "\n";
}
};
int main()
{
// Create tree object
BinaryTree tree1 = BinaryTree();
BinaryTree tree2 = BinaryTree();
//
// ----------------------------
// 8
// / \
// 2 7
// / \ / \
// 6 9 4 5
// / \ / \
// 1 3 23 90
// -------------------------------
// Inorder sequence: 1 6 3 2 9 8 4 7 23 5 90
// Preorder sequence: 8 2 6 1 3 9 7 4 5 23 90
//
int inorder1[] = {
1 , 6 , 3 , 2 , 9 , 8 , 4 , 7 , 23 , 5 , 90
};
int preorder1[] = {
8 , 2 , 6 , 1 , 3 , 9 , 7 , 4 , 5 , 23 , 90
};
// Get the size of arrays
int n1 = sizeof(inorder1) / sizeof(inorder1[0]);
int n2 = sizeof(preorder1) / sizeof(preorder1[0]);
tree1.make_tree(inorder1, preorder1, n1, n2);
tree1.print_tree();
// --------------
// 1
// / \
// 2 3
// / \ / \
// 4 5 9 7
// ----------------
int inorder2[] = {
4 , 2 , 5 , 1 , 9 , 3 , 7
};
int preorder2[] = {
1 , 2 , 4 , 5 , 3 , 9 , 7
};
// Get the size of arrays
n1 = sizeof(inorder2) / sizeof(inorder2[0]);
n2 = sizeof(preorder2) / sizeof(preorder2[0]);
tree2.make_tree(inorder2, preorder2, n1, n2);
tree2.print_tree();
return 0;
}Output
Preorder : 8 2 6 1 3 9 7 4 5 23 90
Inorder : 1 6 3 2 9 8 4 7 23 5 90
Postorder : 1 3 6 9 2 4 23 90 5 7 8
Preorder : 1 2 4 5 3 9 7
Inorder : 4 2 5 1 9 3 7
Postorder : 4 5 2 9 7 3 1// Include namespace system
using System;
// C# Program
// Construct Tree from given Inorder and Preorder traversals
// Binary Tree node
public class Node
{
public int data;
public Node left;
public Node right;
public Node(int data)
{
// Set node value
this.data = data;
this.left = null;
this.right = null;
}
}
// Define Binary Tree
public class BinaryTree
{
public Node root;
public int location;
public BinaryTree()
{
// Set root of tree
this.root = null;
this.location = 0;
}
// Display inorder elements
public void print_inorder(Node node)
{
if (node != null)
{
print_inorder(node.left);
// Print node value
Console.Write(" " + node.data);
print_inorder(node.right);
}
}
// Display pre order elements
public void print_preorder(Node node)
{
if (node != null)
{
// Print node value
Console.Write(" " + node.data);
print_preorder(node.left);
print_preorder(node.right);
}
}
// Display postorder elements
public void print_postorder(Node node)
{
if (node != null)
{
print_postorder(node.left);
print_postorder(node.right);
// Print node value
Console.Write(" " + node.data);
}
}
// Constructing a binary tree from given inorder and preorder
public Node construct_tree(int[] inorder, int[] preorder, int first, int last, int size)
{
if (this.location > size || first > last)
{
return null;
}
Node node = null;
for (int i = first; i <= last && node == null; ++i)
{
// Find node
if (preorder[location] == inorder[i])
{
// Create node
node = new Node(inorder[i]);
// next element of preorder
this.location = this.location + 1;
// Recursively constructing left and right subtree
node.left = construct_tree(inorder, preorder, first, i - 1, size);
node.right = construct_tree(inorder, preorder, i + 1, last, size);
}
}
return node;
}
// handles the request of construct binary tree
public void make_tree(int[] inorder, int[] preorder, int n1, int n2)
{
if (n1 != n2)
{
// Invalid sequence
this.root = null;
}
else
{
this.location = 0;
this.root = construct_tree(inorder, preorder, 0, n1 - 1, n2 - 1);
}
}
// Handles the request of display the element of tree
public void print_tree()
{
if (this.root == null)
{
Console.Write("\n Empty Tree\n");
return;
}
Console.Write("\n Preorder : ");
print_preorder(root);
Console.Write("\n Inorder : ");
print_inorder(root);
Console.Write("\n Postorder : ");
print_postorder(root);
Console.Write("\n");
}
public static void Main(String[] args)
{
// Create tree object
BinaryTree tree1 = new BinaryTree();
BinaryTree tree2 = new BinaryTree();
//
// ----------------------------
// 8
// / \
// 2 7
// / \ / \
// 6 9 4 5
// / \ / \
// 1 3 23 90
// -------------------------------
// Inorder sequence: 1 6 3 2 9 8 4 7 23 5 90
// Preorder sequence: 8 2 6 1 3 9 7 4 5 23 90
//
int[] inorder1 = {
1 , 6 , 3 , 2 , 9 , 8 , 4 , 7 , 23 , 5 , 90
};
int[] preorder1 = {
8 , 2 , 6 , 1 , 3 , 9 , 7 , 4 , 5 , 23 , 90
};
// Get the size of arrays
int n1 = inorder1.Length;
int n2 = preorder1.Length;
tree1.make_tree(inorder1, preorder1, n1, n2);
tree1.print_tree();
//
// --------------
// 1
// / \
// 2 3
// / \ / \
// 4 5 9 7
// ----------------
//
int[] inorder2 = {
4 , 2 , 5 , 1 , 9 , 3 , 7
};
int[] preorder2 = {
1 , 2 , 4 , 5 , 3 , 9 , 7
};
// Get the size of arrays
n1 = inorder2.Length;
n2 = preorder2.Length;
tree2.make_tree(inorder2, preorder2, n1, n2);
tree2.print_tree();
}
}Output
Preorder : 8 2 6 1 3 9 7 4 5 23 90
Inorder : 1 6 3 2 9 8 4 7 23 5 90
Postorder : 1 3 6 9 2 4 23 90 5 7 8
Preorder : 1 2 4 5 3 9 7
Inorder : 4 2 5 1 9 3 7
Postorder : 4 5 2 9 7 3 1<?php
// Php Program
// Construct Tree from given Inorder and Preorder traversals
// Binary Tree node
class Node
{
public $data;
public $left;
public $right;
function __construct($data)
{
// Set node value
$this->data = $data;
$this->left = null;
$this->right = null;
}
}
// Define Binary Tree
class BinaryTree
{
public $root;
public $location;
function __construct()
{
// Set root of tree
$this->root = null;
$this->location = 0;
}
// Display inorder elements
public function print_inorder($node)
{
if ($node != null)
{
$this->print_inorder($node->left);
// Print node value
echo " ". $node->data;
$this->print_inorder($node->right);
}
}
// Display pre order elements
public function print_preorder($node)
{
if ($node != null)
{
// Print node value
echo " ". $node->data;
$this->print_preorder($node->left);
$this->print_preorder($node->right);
}
}
// Display postorder elements
public function print_postorder($node)
{
if ($node != null)
{
$this->print_postorder($node->left);
$this->print_postorder($node->right);
// Print node value
echo " ". $node->data;
}
}
// Constructing a binary tree from given inorder and preorder
public function construct_tree( & $inorder, & $preorder, $first, $last, $size)
{
if ($this->location > $size || $first > $last)
{
return null;
}
$node = null;
for ($i = $first; $i <= $last && $node == null; ++$i)
{
// Find node
if ($preorder[$this->location] == $inorder[$i])
{
// Create node
$node = new Node($inorder[$i]);
// next element of preorder
$this->location = $this->location + 1;
// Recursively constructing left and right subtree
$node->left = $this->construct_tree($inorder, $preorder, $first, $i - 1, $size);
$node->right = $this->construct_tree($inorder, $preorder, $i + 1, $last, $size);
}
}
return $node;
}
// handles the request of construct binary tree
public function make_tree( & $inorder, & $preorder, $n1, $n2)
{
if ($n1 != $n2)
{
// Invalid sequence
$this->root = null;
}
else
{
$this->location = 0;
$this->root = $this->construct_tree($inorder, $preorder, 0, $n1 - 1, $n2 - 1);
}
}
// Handles the request of display the element of tree
public function print_tree()
{
if ($this->root == null)
{
echo "\n Empty Tree\n";
return;
}
echo "\n Preorder : ";
$this->print_preorder($this->root);
echo "\n Inorder : ";
$this->print_inorder($this->root);
echo "\n Postorder : ";
$this->print_postorder($this->root);
echo "\n";
}
}
function main()
{
// Create tree object
$tree1 = new BinaryTree();
$tree2 = new BinaryTree();
//
// ----------------------------
// 8
// / \
// 2 7
// / \ / \
// 6 9 4 5
// / \ / \
// 1 3 23 90
// -------------------------------
// Inorder sequence: 1 6 3 2 9 8 4 7 23 5 90
// Preorder sequence: 8 2 6 1 3 9 7 4 5 23 90
//
$inorder1 = array(1, 6, 3, 2, 9, 8, 4, 7, 23, 5, 90);
$preorder1 = array(8, 2, 6, 1, 3, 9, 7, 4, 5, 23, 90);
// Get the size of arrays
$n1 = count($inorder1);
$n2 = count($preorder1);
$tree1->make_tree($inorder1, $preorder1, $n1, $n2);
$tree1->print_tree();
//
// --------------
// 1
// / \
// 2 3
// / \ / \
// 4 5 9 7
// ----------------
//
$inorder2 = array(4, 2, 5, 1, 9, 3, 7);
$preorder2 = array(1, 2, 4, 5, 3, 9, 7);
// Get the size of arrays
$n1 = count($inorder2);
$n2 = count($preorder2);
$tree2->make_tree($inorder2, $preorder2, $n1, $n2);
$tree2->print_tree();
}
main();Output
Preorder : 8 2 6 1 3 9 7 4 5 23 90
Inorder : 1 6 3 2 9 8 4 7 23 5 90
Postorder : 1 3 6 9 2 4 23 90 5 7 8
Preorder : 1 2 4 5 3 9 7
Inorder : 4 2 5 1 9 3 7
Postorder : 4 5 2 9 7 3 1// Node Js Program
// Construct Tree from given Inorder and Preorder traversals
// Binary Tree node
class Node
{
constructor(data)
{
// Set node value
this.data = data;
this.left = null;
this.right = null;
}
}
// Define Binary Tree
class BinaryTree
{
constructor()
{
// Set root of tree
this.root = null;
this.location = 0;
}
// Display inorder elements
print_inorder(node)
{
if (node != null)
{
this.print_inorder(node.left);
// Print node value
process.stdout.write(" " + node.data);
this.print_inorder(node.right);
}
}
// Display pre order elements
print_preorder(node)
{
if (node != null)
{
// Print node value
process.stdout.write(" " + node.data);
this.print_preorder(node.left);
this.print_preorder(node.right);
}
}
// Display postorder elements
print_postorder(node)
{
if (node != null)
{
this.print_postorder(node.left);
this.print_postorder(node.right);
// Print node value
process.stdout.write(" " + node.data);
}
}
// Constructing a binary tree from given inorder and preorder
construct_tree(inorder, preorder, first, last, size)
{
if (this.location > size || first > last)
{
return null;
}
var node = null;
for (var i = first; i <= last && node == null; ++i)
{
// Find node
if (preorder[this.location] == inorder[i])
{
// Create node
node = new Node(inorder[i]);
// next element of preorder
this.location = this.location + 1;
// Recursively constructing left and right subtree
node.left = this.construct_tree(inorder, preorder, first, i - 1, size);
node.right = this.construct_tree(inorder, preorder, i + 1, last, size);
}
}
return node;
}
// handles the request of construct binary tree
make_tree(inorder, preorder, n1, n2)
{
if (n1 != n2)
{
// Invalid sequence
this.root = null;
}
else
{
this.location = 0;
this.root = this.construct_tree(inorder, preorder, 0, n1 - 1, n2 - 1);
}
}
// Handles the request of display the element of tree
print_tree()
{
if (this.root == null)
{
process.stdout.write("\n Empty Tree\n");
return;
}
process.stdout.write("\n Preorder : ");
this.print_preorder(this.root);
process.stdout.write("\n Inorder : ");
this.print_inorder(this.root);
process.stdout.write("\n Postorder : ");
this.print_postorder(this.root);
process.stdout.write("\n");
}
}
function main()
{
// Create tree object
var tree1 = new BinaryTree();
var tree2 = new BinaryTree();
//
// ----------------------------
// 8
// / \
// 2 7
// / \ / \
// 6 9 4 5
// / \ / \
// 1 3 23 90
// -------------------------------
// Inorder sequence: 1 6 3 2 9 8 4 7 23 5 90
// Preorder sequence: 8 2 6 1 3 9 7 4 5 23 90
//
var inorder1 = [1, 6, 3, 2, 9, 8, 4, 7, 23, 5, 90];
var preorder1 = [8, 2, 6, 1, 3, 9, 7, 4, 5, 23, 90];
// Get the size of arrays
var n1 = inorder1.length;
var n2 = preorder1.length;
tree1.make_tree(inorder1, preorder1, n1, n2);
tree1.print_tree();
//
// --------------
// 1
// / \
// 2 3
// / \ / \
// 4 5 9 7
// ----------------
//
var inorder2 = [4, 2, 5, 1, 9, 3, 7];
var preorder2 = [1, 2, 4, 5, 3, 9, 7];
// Get the size of arrays
n1 = inorder2.length;
n2 = preorder2.length;
tree2.make_tree(inorder2, preorder2, n1, n2);
tree2.print_tree();
}
main();Output
Preorder : 8 2 6 1 3 9 7 4 5 23 90
Inorder : 1 6 3 2 9 8 4 7 23 5 90
Postorder : 1 3 6 9 2 4 23 90 5 7 8
Preorder : 1 2 4 5 3 9 7
Inorder : 4 2 5 1 9 3 7
Postorder : 4 5 2 9 7 3 1# Python 3 Program
# Construct Tree from given Inorder and Preorder traversals
# Binary Tree node
class Node :
def __init__(self, data) :
# Set node value
self.data = data
self.left = None
self.right = None
# Define Binary Tree
class BinaryTree :
def __init__(self) :
# Set root of tree
self.root = None
self.location = 0
# Display inorder elements
def print_inorder(self, node) :
if (node != None) :
self.print_inorder(node.left)
# Print node value
print(" ", node.data, end = "")
self.print_inorder(node.right)
# Display pre order elements
def print_preorder(self, node) :
if (node != None) :
# Print node value
print(" ", node.data, end = "")
self.print_preorder(node.left)
self.print_preorder(node.right)
# Display postorder elements
def print_postorder(self, node) :
if (node != None) :
self.print_postorder(node.left)
self.print_postorder(node.right)
# Print node value
print(" ", node.data, end = "")
# Constructing a binary tree from given inorder and preorder
def construct_tree(self, inorder, preorder, first, last, size) :
if (self.location > size or first > last) :
return None
node = None
i = first
while (i <= last and node == None) :
# Find node
if (preorder[self.location] == inorder[i]) :
# Create node
node = Node(inorder[i])
# next element of preorder
self.location = self.location + 1
# Recursively constructing left and right subtree
node.left = self.construct_tree(inorder, preorder, first, i - 1, size)
node.right = self.construct_tree(inorder, preorder, i + 1, last, size)
i += 1
return node
# handles the request of construct binary tree
def make_tree(self, inorder, preorder, n1, n2) :
if (n1 != n2) :
# Invalid sequence
self.root = None
else :
self.location = 0
self.root = self.construct_tree(inorder, preorder, 0, n1 - 1, n2 - 1)
# Handles the request of display the element of tree
def print_tree(self) :
if (self.root == None) :
print("\n Empty Tree\n", end = "")
return
print("\n Preorder : ", end = "")
self.print_preorder(self.root)
print("\n Inorder : ", end = "")
self.print_inorder(self.root)
print("\n Postorder : ", end = "")
self.print_postorder(self.root)
print("\n", end = "")
def main() :
# Create tree object
tree1 = BinaryTree()
tree2 = BinaryTree()
#
# ----------------------------
# 8
# / \
# 2 7
# / \ / \
# 6 9 4 5
# / \ / \
# 1 3 23 90
# -------------------------------
# Inorder sequence: 1 6 3 2 9 8 4 7 23 5 90
# Preorder sequence: 8 2 6 1 3 9 7 4 5 23 90
#
inorder1 = [1, 6, 3, 2, 9, 8, 4, 7, 23, 5, 90]
preorder1 = [8, 2, 6, 1, 3, 9, 7, 4, 5, 23, 90]
# Get the size of arrays
n1 = len(inorder1)
n2 = len(preorder1)
tree1.make_tree(inorder1, preorder1, n1, n2)
tree1.print_tree()
#
# --------------
# 1
# / \
# 2 3
# / \ / \
# 4 5 9 7
# ----------------
#
inorder2 = [4, 2, 5, 1, 9, 3, 7]
preorder2 = [1, 2, 4, 5, 3, 9, 7]
# Get the size of arrays
n1 = len(inorder2)
n2 = len(preorder2)
tree2.make_tree(inorder2, preorder2, n1, n2)
tree2.print_tree()
if __name__ == "__main__": main()Output
Preorder : 8 2 6 1 3 9 7 4 5 23 90
Inorder : 1 6 3 2 9 8 4 7 23 5 90
Postorder : 1 3 6 9 2 4 23 90 5 7 8
Preorder : 1 2 4 5 3 9 7
Inorder : 4 2 5 1 9 3 7
Postorder : 4 5 2 9 7 3 1# Ruby Program
# Construct Tree from given Inorder and Preorder traversals
# 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)
# Set node value
self.data = data
self.left = nil
self.right = nil
end
end
# Define Binary Tree
class BinaryTree
# Define the accessor and reader of class BinaryTree
attr_reader :root, :location
attr_accessor :root, :location
def initialize()
# Set root of tree
self.root = nil
self.location = 0
end
# Display inorder elements
def print_inorder(node)
if (node != nil)
self.print_inorder(node.left)
# Print node value
print(" ", node.data)
self.print_inorder(node.right)
end
end
# Display pre order elements
def print_preorder(node)
if (node != nil)
# Print node value
print(" ", node.data)
self.print_preorder(node.left)
self.print_preorder(node.right)
end
end
# Display postorder elements
def print_postorder(node)
if (node != nil)
self.print_postorder(node.left)
self.print_postorder(node.right)
# Print node value
print(" ", node.data)
end
end
# Constructing a binary tree from given inorder and preorder
def construct_tree(inorder, preorder, first, last, size)
if (self.location > size || first > last)
return nil
end
node = nil
i = first
while (i <= last && node == nil)
# Find node
if (preorder[location] == inorder[i])
# Create node
node = Node.new(inorder[i])
# next element of preorder
self.location = self.location + 1
# Recursively constructing left and right subtree
node.left = self.construct_tree(inorder, preorder, first, i - 1, size)
node.right = self.construct_tree(inorder, preorder, i + 1, last, size)
end
i += 1
end
return node
end
# handles the request of construct binary tree
def make_tree(inorder, preorder, n1, n2)
if (n1 != n2)
# Invalid sequence
self.root = nil
else
self.location = 0
self.root = self.construct_tree(inorder, preorder, 0, n1 - 1, n2 - 1)
end
end
# Handles the request of display the element of tree
def print_tree()
if (self.root == nil)
print("\n Empty Tree\n")
return
end
print("\n Preorder : ")
self.print_preorder(root)
print("\n Inorder : ")
self.print_inorder(root)
print("\n Postorder : ")
self.print_postorder(root)
print("\n")
end
end
def main()
# Create tree object
tree1 = BinaryTree.new()
tree2 = BinaryTree.new()
#
# ----------------------------
# 8
# / \
# 2 7
# / \ / \
# 6 9 4 5
# / \ / \
# 1 3 23 90
# -------------------------------
# Inorder sequence: 1 6 3 2 9 8 4 7 23 5 90
# Preorder sequence: 8 2 6 1 3 9 7 4 5 23 90
#
inorder1 = [1, 6, 3, 2, 9, 8, 4, 7, 23, 5, 90]
preorder1 = [8, 2, 6, 1, 3, 9, 7, 4, 5, 23, 90]
# Get the size of arrays
n1 = inorder1.length
n2 = preorder1.length
tree1.make_tree(inorder1, preorder1, n1, n2)
tree1.print_tree()
#
# --------------
# 1
# / \
# 2 3
# / \ / \
# 4 5 9 7
# ----------------
#
inorder2 = [4, 2, 5, 1, 9, 3, 7]
preorder2 = [1, 2, 4, 5, 3, 9, 7]
# Get the size of arrays
n1 = inorder2.length
n2 = preorder2.length
tree2.make_tree(inorder2, preorder2, n1, n2)
tree2.print_tree()
end
main()Output
Preorder : 8 2 6 1 3 9 7 4 5 23 90
Inorder : 1 6 3 2 9 8 4 7 23 5 90
Postorder : 1 3 6 9 2 4 23 90 5 7 8
Preorder : 1 2 4 5 3 9 7
Inorder : 4 2 5 1 9 3 7
Postorder : 4 5 2 9 7 3 1
// Scala Program
// Construct Tree from given Inorder and Preorder traversals
// Binary Tree node
class Node(var data: Int , var left: Node , var right: Node)
{
def this(data: Int)
{
this(data, null, null);
}
}
// Define Binary Tree
class BinaryTree(var root: Node , var location: Int)
{
def this()
{
this(null, 0);
}
// Display inorder elements
def print_inorder(node: Node): Unit = {
if (node != null)
{
print_inorder(node.left);
// Print node value
print(" " + node.data);
print_inorder(node.right);
}
}
// Display pre order elements
def print_preorder(node: Node): Unit = {
if (node != null)
{
// Print node value
print(" " + node.data);
print_preorder(node.left);
print_preorder(node.right);
}
}
// Display postorder elements
def print_postorder(node: Node): Unit = {
if (node != null)
{
print_postorder(node.left);
print_postorder(node.right);
// Print node value
print(" " + node.data);
}
}
// Constructing a binary tree from given inorder and preorder
def construct_tree(inorder: Array[Int], preorder: Array[Int], first: Int, last: Int, size: Int): Node = {
if (this.location > size || first > last)
{
return null;
}
var node: Node = null;
var i: Int = first;
while (i <= last && node == null)
{
// Find node
if (preorder(location) == inorder(i))
{
// Create node
node = new Node(inorder(i));
// next element of preorder
this.location = this.location + 1;
// Recursively constructing left and right subtree
node.left = construct_tree(inorder, preorder, first, i - 1, size);
node.right = construct_tree(inorder, preorder, i + 1, last, size);
}
i += 1;
}
return node;
}
// handles the request of construct binary tree
def make_tree(inorder: Array[Int], preorder: Array[Int], n1: Int, n2: Int): Unit = {
if (n1 != n2)
{
// Invalid sequence
this.root = null;
}
else
{
this.location = 0;
this.root = construct_tree(inorder, preorder, 0, n1 - 1, n2 - 1);
}
}
// Handles the request of display the element of tree
def print_tree(): Unit = {
if (this.root == null)
{
print("\n Empty Tree\n");
return;
}
print("\n Preorder : ");
print_preorder(root);
print("\n Inorder : ");
print_inorder(root);
print("\n Postorder : ");
print_postorder(root);
print("\n");
}
}
object Main
{
def main(args: Array[String]): Unit = {
// Create tree object
var tree1: BinaryTree = new BinaryTree();
var tree2: BinaryTree = new BinaryTree();
//
// ----------------------------
// 8
// / \
// 2 7
// / \ / \
// 6 9 4 5
// / \ / \
// 1 3 23 90
// -------------------------------
// Inorder sequence: 1 6 3 2 9 8 4 7 23 5 90
// Preorder sequence: 8 2 6 1 3 9 7 4 5 23 90
//
var inorder1: Array[Int] = Array(1, 6, 3, 2, 9, 8, 4, 7, 23, 5, 90);
var preorder1: Array[Int] = Array(8, 2, 6, 1, 3, 9, 7, 4, 5, 23, 90);
// Get the size of arrays
var n1: Int = inorder1.length;
var n2: Int = preorder1.length;
tree1.make_tree(inorder1, preorder1, n1, n2);
tree1.print_tree();
//
// --------------
// 1
// / \
// 2 3
// / \ / \
// 4 5 9 7
// ----------------
//
var inorder2: Array[Int] = Array(4, 2, 5, 1, 9, 3, 7);
var preorder2: Array[Int] = Array(1, 2, 4, 5, 3, 9, 7);
// Get the size of arrays
n1 = inorder2.length;
n2 = preorder2.length;
tree2.make_tree(inorder2, preorder2, n1, n2);
tree2.print_tree();
}
}Output
Preorder : 8 2 6 1 3 9 7 4 5 23 90
Inorder : 1 6 3 2 9 8 4 7 23 5 90
Postorder : 1 3 6 9 2 4 23 90 5 7 8
Preorder : 1 2 4 5 3 9 7
Inorder : 4 2 5 1 9 3 7
Postorder : 4 5 2 9 7 3 1// Swift 4 Program
// Construct Tree from given Inorder and Preorder traversals
// Binary Tree node
class Node
{
var data: Int;
var left: Node? ;
var right: Node? ;
init(_ data: Int)
{
// Set node value
self.data = data;
self.left = nil;
self.right = nil;
}
}
// Define Binary Tree
class BinaryTree
{
var root: Node? ;
var location: Int;
init()
{
// Set root of tree
self.root = nil;
self.location = 0;
}
// Display inorder elements
func print_inorder(_ node: Node? )
{
if (node != nil)
{
self.print_inorder(node!.left);
// Print node value
print(" ", node!.data, terminator: "");
self.print_inorder(node!.right);
}
}
// Display pre order elements
func print_preorder(_ node: Node? )
{
if (node != nil)
{
// Print node value
print(" ", node!.data, terminator: "");
self.print_preorder(node!.left);
self.print_preorder(node!.right);
}
}
// Display postorder elements
func print_postorder(_ node: Node? )
{
if (node != nil)
{
self.print_postorder(node!.left);
self.print_postorder(node!.right);
// Print node value
print(" ", node!.data, terminator: "");
}
}
// Constructing a binary tree from given inorder and preorder
func construct_tree(_ inorder: [Int], _ preorder: [Int], _ first: Int, _ last: Int, _ size: Int)->Node?
{
if (self.location > size || first > last)
{
return nil;
}
var node: Node? = nil;
var i: Int = first;
while (i <= last && node == nil)
{
// Find node
if (preorder[self.location] == inorder[i])
{
// Create node
node = Node(inorder[i]);
// next element of preorder
self.location = self.location + 1;
// Recursively constructing left and right subtree
node!.left = self.construct_tree(inorder, preorder, first, i - 1, size);
node!.right = self.construct_tree(inorder, preorder, i + 1, last, size);
}
i += 1;
}
return node;
}
// handles the request of construct binary tree
func make_tree(_ inorder: [Int], _ preorder: [Int], _ n1: Int, _ n2: Int)
{
if (n1 != n2)
{
// Invalid sequence
self.root = nil;
}
else
{
self.location = 0;
self.root = self.construct_tree(inorder, preorder, 0, n1 - 1, n2 - 1);
}
}
// Handles the request of display the element of tree
func print_tree()
{
if (self.root == nil)
{
print("\n Empty Tree\n", terminator: "");
return;
}
print("\n Preorder : ", terminator: "");
self.print_preorder(self.root);
print("\n Inorder : ", terminator: "");
self.print_inorder(self.root);
print("\n Postorder : ", terminator: "");
self.print_postorder(self.root);
print("\n", terminator: "");
}
}
func main()
{
// Create tree object
let tree1: BinaryTree = BinaryTree();
let tree2: BinaryTree = BinaryTree();
//
// ----------------------------
// 8
// / \
// 2 7
// / \ / \
// 6 9 4 5
// / \ / \
// 1 3 23 90
// -------------------------------
// Inorder sequence: 1 6 3 2 9 8 4 7 23 5 90
// Preorder sequence: 8 2 6 1 3 9 7 4 5 23 90
//
let inorder1: [Int] = [1, 6, 3, 2, 9, 8, 4, 7, 23, 5, 90];
let preorder1: [Int] = [8, 2, 6, 1, 3, 9, 7, 4, 5, 23, 90];
// Get the size of arrays
var n1: Int = inorder1.count;
var n2: Int = preorder1.count;
tree1.make_tree(inorder1, preorder1, n1, n2);
tree1.print_tree();
//
// --------------
// 1
// / \
// 2 3
// / \ / \
// 4 5 9 7
// ----------------
//
let inorder2: [Int] = [4, 2, 5, 1, 9, 3, 7];
let preorder2: [Int] = [1, 2, 4, 5, 3, 9, 7];
// Get the size of arrays
n1 = inorder2.count;
n2 = preorder2.count;
tree2.make_tree(inorder2, preorder2, n1, n2);
tree2.print_tree();
}
main();Output
Preorder : 8 2 6 1 3 9 7 4 5 23 90
Inorder : 1 6 3 2 9 8 4 7 23 5 90
Postorder : 1 3 6 9 2 4 23 90 5 7 8
Preorder : 1 2 4 5 3 9 7
Inorder : 4 2 5 1 9 3 7
Postorder : 4 5 2 9 7 3 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