Construct Tree from given Inorder and Postorder

Construct Tree using given Inorder and Postorder

Here given code implementation process.

/*
    C Program 
    Construct binary tree from inorder and postorder traversal
*/
#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 postorder
struct Node *construct_tree(int inorder[], int postorder[], int first, int last, int *location)
{
	if ( *location < 0 || first > last)
	{
		return NULL;
	}
	struct Node *node = NULL;
	for (int i = first; i <= last && node == NULL; ++i)
	{
		//Find node
		if (postorder[ *location] == inorder[i])
		{
			// Create node
			node = get_node(inorder[i]);
			// next element of postorder
			*location = *location - 1;
			//Recursively constructing left and right subtree
			node->right = construct_tree(inorder, postorder, i + 1, last, location);
			node->left = construct_tree(inorder, postorder, first, i - 1, location);
		}
	}
	return node;
}
//handles the request of construct binary tree
struct Node *make_tree(int inorder[], int postorder[], int n1, int n2)
{
	if (n1 != n2)
	{
		//Invalid sequence
		return NULL;
	}
	else
	{
		int location = n2 - 1;
		return construct_tree(inorder, postorder, 0, n1 - 1, & location);
	}
}
//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()
{
	/*
	--------------
	        1
	      /   \
	     2     3 
	    / \   / \
	   4   5 9   7
	----------------  
	  
	*/
	int inorder[] = {
		4 , 2 , 5 , 1 , 9 , 3 , 7
	};
	int postorder[] = {
		4 , 5 , 2 , 9 , 7 , 3 , 1
	};
	// Get the size of arrays
	int n1 = sizeof(inorder) / sizeof(inorder[0]);
	int n2 = sizeof(postorder) / sizeof(postorder[0]);
	struct Node *root = make_tree(inorder, postorder, n1, n2);
	print_tree(root);
	return 0;
}

Output

 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 binary tree from inorder and postorder traversal
*/

// 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 postorder
	public Node construct_tree(int[] inorder, int[] postorder, int first, int last)
	{
		if (location < 0 || first > last)
		{
			return null;
		}
		Node node = null;
		for (int i = first; i <= last && node == null; ++i)
		{
			//Find node
			if (postorder[location] == inorder[i])
			{
				// Create node
				node = new Node(inorder[i]);
				// next element of postorder
				this.location = this.location - 1;
				//Recursively constructing left and right subtree
				node.right = construct_tree(inorder, postorder, i + 1, last);
				node.left = construct_tree(inorder, postorder, first, i - 1);
			}
		}
		return node;
	}
	//handles the request of construct binary tree
	public void make_tree(int[] inorder, int[] postorder, int n1, int n2)
	{
		if (n1 != n2)
		{
			//Invalid sequence
			this.root = null;
		}
		else
		{
			this.location = n2 - 1;
			this.root = construct_tree(inorder, postorder, 0, n1 - 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 tree = new BinaryTree();
		/*
        --------------
                1
              /   \
             2     3 
            / \   / \
           4   5 9   7
        ----------------  
          
        */
		int[] inorder = {
			4 , 2 , 5 , 1 , 9 , 3 , 7
		};
		int[] postorder = {
			4 , 5 , 2 , 9 , 7 , 3 , 1
		};
		// Get the size of arrays
		int n1 = inorder.length;
		int n2 = postorder.length;
		tree.make_tree(inorder, postorder, n1, n2);
		tree.print_tree();
	}
}

Output

 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 binary tree from inorder and postorder traversal

//  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 postorder
	Node *construct_tree(int inorder[], int postorder[], int first, int last)
	{
		if (this->location < 0 || first > last)
		{
			return NULL;
		}
		Node *node = NULL;
		for (int i = first; i <= last && node == NULL; ++i)
		{
			// Find node
			if (postorder[this->location] == inorder[i])
			{
				//  Create node
				node = new Node(inorder[i]);
				//  next element of postorder
				this->location = this->location - 1;
				// Recursively constructing left and right subtree
				node->right = this->construct_tree(inorder, postorder, i + 1, last);
				node->left = this->construct_tree(inorder, postorder, first, i - 1);
			}
		}
		return node;
	}
	// handles the request of construct binary tree
	void make_tree(int inorder[], int postorder[], int n1, int n2)
	{
		if (n1 != n2)
		{
			// Invalid sequence
			this->root = NULL;
		}
		else
		{
			this->location = n2 - 1;
			this->root = this->construct_tree(inorder, postorder, 0, n1 - 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 tree = BinaryTree();
	// 
	//         --------------
	//                 1
	//               /   \
	//              2     3 
	//             / \   / \
	//            4   5 9   7
	//         ----------------  
	//           
	//         
	int inorder[] = {
		4 , 2 , 5 , 1 , 9 , 3 , 7
	};
	int postorder[] = {
		4 , 5 , 2 , 9 , 7 , 3 , 1
	};
	//  Get the size of arrays
	int n1 = sizeof(inorder) / sizeof(inorder[0]);
	int n2 = sizeof(postorder) / sizeof(postorder[0]);
	tree.make_tree(inorder, postorder, n1, n2);
	tree.print_tree();
	return 0;
}

Output

 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 binary tree from inorder and postorder traversal

//  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 postorder
	public Node construct_tree(int[] inorder, int[] postorder, int first, int last)
	{
		if (location < 0 || first > last)
		{
			return null;
		}
		Node node = null;
		for (int i = first; i <= last && node == null; ++i)
		{
			// Find node
			if (postorder[location] == inorder[i])
			{
				//  Create node
				node = new Node(inorder[i]);
				//  next element of postorder
				this.location = this.location - 1;
				// Recursively constructing left and right subtree
				node.right = construct_tree(inorder, postorder, i + 1, last);
				node.left = construct_tree(inorder, postorder, first, i - 1);
			}
		}
		return node;
	}
	// handles the request of construct binary tree
	public void make_tree(int[] inorder, int[] postorder, int n1, int n2)
	{
		if (n1 != n2)
		{
			// Invalid sequence
			this.root = null;
		}
		else
		{
			this.location = n2 - 1;
			this.root = construct_tree(inorder, postorder, 0, n1 - 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 tree = new BinaryTree();
		// 
		//         --------------
		//                 1
		//               /   \
		//              2     3 
		//             / \   / \
		//            4   5 9   7
		//         ----------------  
		//           
		//         
		int[] inorder = {
			4 , 2 , 5 , 1 , 9 , 3 , 7
		};
		int[] postorder = {
			4 , 5 , 2 , 9 , 7 , 3 , 1
		};
		//  Get the size of arrays
		int n1 = inorder.Length;
		int n2 = postorder.Length;
		tree.make_tree(inorder, postorder, n1, n2);
		tree.print_tree();
	}
}

Output

 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 binary tree from inorder and postorder traversal

//  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 postorder
	public	function construct_tree( & $inorder, & $postorder, $first, $last)
	{
		if ($this->location < 0 || $first > $last)
		{
			return null;
		}
		$node = null;
		for ($i = $first; $i <= $last && $node == null; ++$i)
		{
			// Find node
			if ($postorder[$this->location] == $inorder[$i])
			{
				//  Create node
				$node = new Node($inorder[$i]);
				//  next element of postorder
				$this->location = $this->location - 1;
				// Recursively constructing left and right subtree
				$node->right = $this->construct_tree($inorder, $postorder, $i + 1, $last);
				$node->left = $this->construct_tree($inorder, $postorder, $first, $i - 1);
			}
		}
		return $node;
	}
	// handles the request of construct binary tree
	public	function make_tree( & $inorder, & $postorder, $n1, $n2)
	{
		if ($n1 != $n2)
		{
			// Invalid sequence
			$this->root = null;
		}
		else
		{
			$this->location = $n2 - 1;
			$this->root = $this->construct_tree($inorder, $postorder, 0, $n1 - 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
	$tree = new BinaryTree();
	// 
	//         --------------
	//                 1
	//               /   \
	//              2     3 
	//             / \   / \
	//            4   5 9   7
	//         ----------------  
	//           
	//         
	$inorder = array(4, 2, 5, 1, 9, 3, 7);
	$postorder = array(4, 5, 2, 9, 7, 3, 1);
	//  Get the size of arrays
	$n1 = count($inorder);
	$n2 = count($postorder);
	$tree->make_tree($inorder, $postorder, $n1, $n2);
	$tree->print_tree();
}
main();

Output

 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 binary tree from inorder and postorder traversal

//  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 postorder
	construct_tree(inorder, postorder, first, last)
	{
		if (this.location < 0 || first > last)
		{
			return null;
		}
		var node = null;
		for (var i = first; i <= last && node == null; ++i)
		{
			// Find node
			if (postorder[this.location] == inorder[i])
			{
				//  Create node
				node = new Node(inorder[i]);
				//  next element of postorder
				this.location = this.location - 1;
				// Recursively constructing left and right subtree
				node.right = this.construct_tree(inorder, postorder, i + 1, last);
				node.left = this.construct_tree(inorder, postorder, first, i - 1);
			}
		}
		return node;
	}
	// handles the request of construct binary tree
	make_tree(inorder, postorder, n1, n2)
	{
		if (n1 != n2)
		{
			// Invalid sequence
			this.root = null;
		}
		else
		{
			this.location = n2 - 1;
			this.root = this.construct_tree(inorder, postorder, 0, n1 - 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 tree = new BinaryTree();
	// 
	//         --------------
	//                 1
	//               /   \
	//              2     3 
	//             / \   / \
	//            4   5 9   7
	//         ----------------  
	//           
	//         
	var inorder = [4, 2, 5, 1, 9, 3, 7];
	var postorder = [4, 5, 2, 9, 7, 3, 1];
	//  Get the size of arrays
	var n1 = inorder.length;
	var n2 = postorder.length;
	tree.make_tree(inorder, postorder, n1, n2);
	tree.print_tree();
}
main();

Output

 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 binary tree from inorder and postorder traversal

#  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 postorder
	def construct_tree(self, inorder, postorder, first, last) :
		if (self.location < 0 or first > last) :
			return None
		
		node = None
		i = first
		while (i <= last and node == None) :
			# Find node
			if (postorder[self.location] == inorder[i]) :
				#  Create node
				node = Node(inorder[i])
				#  next element of postorder
				self.location = self.location - 1
				# Recursively constructing left and right subtree
				node.right = self.construct_tree(inorder, postorder, i + 1, last)
				node.left = self.construct_tree(inorder, postorder, first, i - 1)
			
			i += 1
		
		return node
	
	# handles the request of construct binary tree
	def make_tree(self, inorder, postorder, n1, n2) :
		if (n1 != n2) :
			# Invalid sequence
			self.root = None
		else :
			self.location = n2 - 1
			self.root = self.construct_tree(inorder, postorder, 0, n1 - 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
	tree = BinaryTree()
	# 
	#         --------------
	#                 1
	#               /   \
	#              2     3 
	#             / \   / \
	#            4   5 9   7
	#         ----------------  
	#            Binary Tree
	#         
	
	inorder = [4, 2, 5, 1, 9, 3, 7]
	postorder = [4, 5, 2, 9, 7, 3, 1]
	#  Get the size of arrays
	n1 = len(inorder)
	n2 = len(postorder)
	tree.make_tree(inorder, postorder, n1, n2)
	tree.print_tree()

if __name__ == "__main__": main()

Output

 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 binary tree from inorder and postorder traversal

#  Binary Tree node
class Node  
	# Define the accessor and reader of class Node  
	attr_reader :data, :left, :right
	attr_accessor :data, :left, :right
 
	
	def initialize(data) 
		#  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 postorder
	def construct_tree(inorder, postorder, first, last) 
		if (location < 0 || first > last) 
			return nil
		end

		node = nil
		i = first
		while (i <= last && node == nil) 
			# Find node
			if (postorder[location] == inorder[i]) 
				#  Create node
				node = Node.new(inorder[i])
				#  next element of postorder
				self.location = self.location - 1
				# Recursively constructing left and right subtree
				node.right = self.construct_tree(inorder, postorder, i + 1, last)
				node.left = self.construct_tree(inorder, postorder, first, i - 1)
			end

			i += 1
		end

		return node
	end

	# handles the request of construct binary tree
	def make_tree(inorder, postorder, n1, n2) 
		if (n1 != n2) 
			# Invalid sequence
			self.root = nil
		else 
			self.location = n2 - 1
			self.root = self.construct_tree(inorder, postorder, 0, n1 - 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
	tree = BinaryTree.new()
	# 
	#         --------------
	#                 1
	#               /   \
	#              2     3 
	#             / \   / \
	#            4   5 9   7
	#         ----------------  
	#            Binary Tree
	#         
	
	inorder = [4, 2, 5, 1, 9, 3, 7]
	postorder = [4, 5, 2, 9, 7, 3, 1]
	#  Get the size of arrays
	n1 = inorder.length
	n2 = postorder.length
	tree.make_tree(inorder, postorder, n1, n2)
	tree.print_tree()
end

main()

Output

 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 binary tree from inorder and postorder traversal

//  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 postorder
	def construct_tree(inorder: Array[Int], postorder: Array[Int], first: Int, last: Int): Node = {
		if (location < 0 || first > last)
		{
			return null;
		}
		var node: Node = null;
		var i: Int = first;
		while (i <= last && node == null)
		{
			// Find node
			if (postorder(location) == inorder(i))
			{
				//  Create node
				node = new Node(inorder(i));
				//  next element of postorder
				this.location = this.location - 1;
				// Recursively constructing left and right subtree
				node.right = construct_tree(inorder, postorder, i + 1, last);
				node.left = construct_tree(inorder, postorder, first, i - 1);
			}
			i += 1;
		}
		return node;
	}
	// handles the request of construct binary tree
	def make_tree(inorder: Array[Int], postorder: Array[Int], n1: Int, n2: Int): Unit = {
		if (n1 != n2)
		{
			// Invalid sequence
			this.root = null;
		}
		else
		{
			this.location = n2 - 1;
			this.root = construct_tree(inorder, postorder, 0, n1 - 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 tree: BinaryTree = new BinaryTree();
		// 
		//         --------------
		//                 1
		//               /   \
		//              2     3 
		//             / \   / \
		//            4   5 9   7
		//         ----------------  
		//            Binary Tree
		//         
		var inorder: Array[Int] = Array(4, 2, 5, 1, 9, 3, 7);
		var postorder: Array[Int] = Array(4, 5, 2, 9, 7, 3, 1);
		//  Get the size of arrays
		var n1: Int = inorder.length;
		var n2: Int = postorder.length;
		tree.make_tree(inorder, postorder, n1, n2);
		tree.print_tree();
	}
}

Output

 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 binary tree from inorder and postorder traversal

//  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 postorder
	func construct_tree(_ inorder: [Int], _ postorder: [Int], _ first: Int, _ last: Int)->Node?
	{
		if (self.location < 0 || first > last)
		{
			return nil;
		}
		var node: Node? = nil;
		var i: Int = first;
		while (i <= last && node == nil)
		{
			// Find node
			if (postorder[self.location] == inorder[i])
			{
				//  Create node
				node = Node(inorder[i]);
				//  next element of postorder
				self.location = self.location - 1;
				// Recursively constructing left and right subtree
				node!.right = self.construct_tree(inorder, postorder, i + 1, last);
				node!.left = self.construct_tree(inorder, postorder, first, i - 1);
			}
			i += 1;
		}
		return node;
	}
	// handles the request of construct binary tree
	func make_tree(_ inorder: [Int], _ postorder: [Int], _ n1: Int, _ n2: Int)
	{
		if (n1 != n2)
		{
			// Invalid sequence
			self.root = nil;
		}
		else
		{
			self.location = n2 - 1;
			self.root = self.construct_tree(inorder, postorder, 0, n1 - 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 tree: BinaryTree = BinaryTree();
	// 
	//         --------------
	//                 1
	//               /   \
	//              2     3 
	//             / \   / \
	//            4   5 9   7
	//         ----------------  
	//            Binary Tree
	//         
	let inorder: [Int] = [4, 2, 5, 1, 9, 3, 7];
	let postorder: [Int] = [4, 5, 2, 9, 7, 3, 1];
	//  Get the size of arrays
	let n1: Int = inorder.count;
	let n2: Int = postorder.count;
	tree.make_tree(inorder, postorder, n1, n2);
	tree.print_tree();
}
main();

Output

 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







© 2021, kalkicode.com, All rights reserved