Posted on by Kalkicode
Code Binary Tree

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.

Construct Tree using given Inorder and Preorder

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

Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment