Skip to main content

Construct Special Binary Tree from given Inorder Traversal

Here given code implementation process.

/*
    C Program 
    Construct Special Binary Tree from given Inorder 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
struct Node * construct_tree(int inorder[], int first,int last)
{

    if(first > last)
    {
        return NULL;
    }
    int location = first;

    //Find largest element
    for (int i = first+1; i <= last; ++i)
    {
        if(inorder[i]>inorder[location])
        {
            location = i;
        }
    }

    struct Node*node = get_node(inorder[location]);

    node->left  = construct_tree(inorder,first,location-1);
    node->right = construct_tree(inorder,location+1,last);  

    return node;
}
//handles the request of construct binary tree
struct Node * make_tree(int inorder[], int n)
{
    if(n <= 0)
    {
        //Invalid sequence
        return NULL;
    }
    else
    {
        return construct_tree(inorder,0,n-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()
{
    
    int inorder[]   = {7,2,6,1,8,4,12,9,0,11,3};  
    
    // Get the size
    int n = sizeof(inorder)/sizeof(inorder[0]);

    struct Node *root = make_tree(inorder,n);

    /*
            12
          /   \
         /     \
        /       \
       8        11
      /  \     /  \
     7    4   9    3
      \        \    
       6        0  
      / \
     2   1 
    ----------------  
    Resultant binary tree
    */
    print_tree(root);
    return 0;
}

Output

 Preorder :   12  8  7  6  2  1  4  11  9  0  3
 Inorder :   7  2  6  1  8  4  12  9  0  11  3
 Postorder :   2  1  6  7  4  8  0  9  3  11  12
/*
    Java Program 
    Construct Special Binary Tree from given Inorder 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
	public Node construct_tree(int[] inorder, int first, int last)
	{
		if (first > last)
		{
			return null;
		}
		int location = first;
		//Find largest element
		for (int i = first + 1; i <= last; ++i)
		{
			if (inorder[i] > inorder[location])
			{
				location = i;
			}
		}
		Node node = new Node(inorder[location]);
		//recursively constructing left and right subtree
		node.left = construct_tree(inorder, first, location - 1);
		node.right = construct_tree(inorder, location + 1, last);
		//return node
		return node;
	}
	//handles the request of construct binary tree
	public void make_tree(int[] inorder, int n)
	{
		if (n <= 0)
		{
			//Invalid sequence
			this.root = null;
		}
		else
		{
			this.root = construct_tree(inorder, 0, n - 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();
		int[] inorder = {
			7 , 2 , 6 , 1 , 8 , 4 , 12 , 9 , 0 , 11 , 3
		};
		// Get the size
		int n = inorder.length;
		tree.make_tree(inorder, n);
		/*
		            12
		          /   \
		         /     \
		        /       \
		       8        11
		      /  \     /  \
		     7    4   9    3
		      \        \    
		       6        0  
		      / \
		     2   1 
		    ----------------  
		    Resultant binary tree
		 */
		tree.print_tree();
	}
}

Output

 Preorder :   12  8  7  6  2  1  4  11  9  0  3
 Inorder :   7  2  6  1  8  4  12  9  0  11  3
 Postorder :   2  1  6  7  4  8  0  9  3  11  12
// Include header file
#include <iostream>
using namespace std;
//  C++ Program 
//  Construct Special Binary Tree from given Inorder 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
	Node *construct_tree(int inorder[], int first, int last)
	{
		// return node
		if (first > last)
		{
			return NULL;
		}
		int location = first;
		// Find largest element
		for (int i = first + 1; i <= last; ++i)
		{
			if (inorder[i] > inorder[location])
			{
				location = i;
			}
		}
		Node *node = new Node(inorder[location]);
		// recursively constructing left and right subtree
		node->left = this->construct_tree(inorder, first, location - 1);
		node->right = this->construct_tree(inorder, location + 1, last);
		return node;
	}
	// handles the request of construct binary tree
	void make_tree(int inorder[], int n)
	{
		if (n <= 0)
		{
			// Invalid sequence
			this->root = NULL;
		}
		else
		{
			this->root = this->construct_tree(inorder, 0, n - 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();
	int inorder[] = {
		7 , 2 , 6 , 1 , 8 , 4 , 12 , 9 , 0 , 11 , 3
	};
	//  Get the size
	int n = sizeof(inorder) / sizeof(inorder[0]);
	tree.make_tree(inorder, n);
	// 
	// 		            12
	// 		          /   \
	// 		         /     \
	// 		        /       \
	// 		       8        11
	// 		      /  \     /  \
	// 		     7    4   9    3
	// 		      \        \    
	// 		       6        0  
	// 		      / \
	// 		     2   1 
	// 		    ----------------  
	// 		    Resultant binary tree
	// 		 
	tree.print_tree();
	return 0;
}

Output

 Preorder :   12  8  7  6  2  1  4  11  9  0  3
 Inorder :   7  2  6  1  8  4  12  9  0  11  3
 Postorder :   2  1  6  7  4  8  0  9  3  11  12
// Include namespace system
using System;

//  C# Program 
//  Construct Special Binary Tree from given Inorder 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
	public Node construct_tree(int[] inorder, int first, int last)
	{
		// return node
		if (first > last)
		{
			return null;
		}
		int location = first;
		// Find largest element
		for (int i = first + 1; i <= last; ++i)
		{
			if (inorder[i] > inorder[location])
			{
				location = i;
			}
		}
		Node node = new Node(inorder[location]);
		// recursively constructing left and right subtree
		node.left = construct_tree(inorder, first, location - 1);
		node.right = construct_tree(inorder, location + 1, last);
		return node;
	}
	// handles the request of construct binary tree
	public void make_tree(int[] inorder, int n)
	{
		if (n <= 0)
		{
			// Invalid sequence
			this.root = null;
		}
		else
		{
			this.root = construct_tree(inorder, 0, n - 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();
		int[] inorder = {
			7 , 2 , 6 , 1 , 8 , 4 , 12 , 9 , 0 , 11 , 3
		};
		//  Get the size
		int n = inorder.Length;
		tree.make_tree(inorder, n);
		// 
		// 		            12
		// 		          /   \
		// 		         /     \
		// 		        /       \
		// 		       8        11
		// 		      /  \     /  \
		// 		     7    4   9    3
		// 		      \        \    
		// 		       6        0  
		// 		      / \
		// 		     2   1 
		// 		    ----------------  
		// 		    Resultant binary tree
		// 		 
		tree.print_tree();
	}
}

Output

 Preorder :   12  8  7  6  2  1  4  11  9  0  3
 Inorder :   7  2  6  1  8  4  12  9  0  11  3
 Postorder :   2  1  6  7  4  8  0  9  3  11  12
<?php
//  Php Program 
//  Construct Special Binary Tree from given Inorder 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
	public	function construct_tree( & $inorder, $first, $last)
	{
		// return node
		if ($first > $last)
		{
			return null;
		}
		$location = $first;
		// Find largest element
		for ($i = $first + 1; $i <= $last; ++$i)
		{
			if ($inorder[$i] > $inorder[$location])
			{
				$location = $i;
			}
		}
		$node = new Node($inorder[$location]);
		// recursively constructing left and right subtree
		$node->left = $this->construct_tree($inorder, $first, $location - 1);
		$node->right = $this->construct_tree($inorder, $location + 1, $last);
		return $node;
	}
	// handles the request of construct binary tree
	public	function make_tree( & $inorder, $n)
	{
		if ($n <= 0)
		{
			// Invalid sequence
			$this->root = null;
		}
		else
		{
			$this->root = $this->construct_tree($inorder, 0, $n - 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();
	$inorder = array(7, 2, 6, 1, 8, 4, 12, 9, 0, 11, 3);
	//  Get the size
	$n = count($inorder);
	$tree->make_tree($inorder, $n);
	// 
	// 		            12
	// 		          /   \
	// 		         /     \
	// 		        /       \
	// 		       8        11
	// 		      /  \     /  \
	// 		     7    4   9    3
	// 		      \        \    
	// 		       6        0  
	// 		      / \
	// 		     2   1 
	// 		    ----------------  
	// 		    Resultant binary tree
	// 		 
	$tree->print_tree();
}
main();

Output

 Preorder :   12  8  7  6  2  1  4  11  9  0  3
 Inorder :   7  2  6  1  8  4  12  9  0  11  3
 Postorder :   2  1  6  7  4  8  0  9  3  11  12
//  Node Js Program 
//  Construct Special Binary Tree from given Inorder 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
	construct_tree(inorder, first, last)
	{
		// return node
		if (first > last)
		{
			return null;
		}
		var location = first;
		// Find largest element
		for (var i = first + 1; i <= last; ++i)
		{
			if (inorder[i] > inorder[location])
			{
				location = i;
			}
		}
		var node = new Node(inorder[location]);
		// recursively constructing left and right subtree
		node.left = this.construct_tree(inorder, first, location - 1);
		node.right = this.construct_tree(inorder, location + 1, last);
		return node;
	}
	// handles the request of construct binary tree
	make_tree(inorder, n)
	{
		if (n <= 0)
		{
			// Invalid sequence
			this.root = null;
		}
		else
		{
			this.root = this.construct_tree(inorder, 0, n - 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();
	var inorder = [7, 2, 6, 1, 8, 4, 12, 9, 0, 11, 3];
	//  Get the size
	var n = inorder.length;
	tree.make_tree(inorder, n);
	// 
	// 		            12
	// 		          /   \
	// 		         /     \
	// 		        /       \
	// 		       8        11
	// 		      /  \     /  \
	// 		     7    4   9    3
	// 		      \        \    
	// 		       6        0  
	// 		      / \
	// 		     2   1 
	// 		    ----------------  
	// 		    Resultant binary tree
	// 		 
	tree.print_tree();
}
main();

Output

 Preorder :   12  8  7  6  2  1  4  11  9  0  3
 Inorder :   7  2  6  1  8  4  12  9  0  11  3
 Postorder :   2  1  6  7  4  8  0  9  3  11  12
#  Python 3 Program 
#  Construct Special Binary Tree from given Inorder 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
	def construct_tree(self, inorder, first, last) :
		if (first > last) :
			return None
		
		location = first
		i = first + 1
		# Find largest element
		while (i <= last) :
			if (inorder[i] > inorder[location]) :
				location = i
			
			i += 1
		
		node = Node(inorder[location])
		# recursively constructing left and right subtree
		node.left = self.construct_tree(inorder, first, location - 1)
		node.right = self.construct_tree(inorder, location + 1, last)
		# return node
		return node
	
	# handles the request of construct binary tree
	def make_tree(self, inorder, n) :
		if (n <= 0) :
			# Invalid sequence
			self.root = None
		else :
			self.root = self.construct_tree(inorder, 0, n - 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()
	inorder = [7, 2, 6, 1, 8, 4, 12, 9, 0, 11, 3]
	#  Get the size
	n = len(inorder)
	tree.make_tree(inorder, n)
	# 
	# 		            12
	# 		          /   \
	# 		         /     \
	# 		        /       \
	# 		       8        11
	# 		      /  \     /  \
	# 		     7    4   9    3
	# 		      \        \    
	# 		       6        0  
	# 		      / \
	# 		     2   1 
	# 		    ----------------  
	# 		    Resultant binary tree
	# 		 
	
	tree.print_tree()

if __name__ == "__main__": main()

Output

 Preorder :    12   8   7   6   2   1   4   11   9   0   3
 Inorder :    7   2   6   1   8   4   12   9   0   11   3
 Postorder :    2   1   6   7   4   8   0   9   3   11   12
#  Ruby Program 
#  Construct Special Binary Tree from given Inorder 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
	def construct_tree(inorder, first, last) 
		if (first > last) 
			return nil
		end

		location = first
		i = first + 1
		# Find largest element
		while (i <= last) 
			if (inorder[i] > inorder[location]) 
				location = i
			end

			i += 1
		end

		node = Node.new(inorder[location])
		# recursively constructing left and right subtree
		node.left = self.construct_tree(inorder, first, location - 1)
		node.right = self.construct_tree(inorder, location + 1, last)
		# return node
		return node
	end

	# handles the request of construct binary tree
	def make_tree(inorder, n) 
		if (n <= 0) 
			# Invalid sequence
			self.root = nil
		else 
			self.root = self.construct_tree(inorder, 0, n - 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()
	inorder = [7, 2, 6, 1, 8, 4, 12, 9, 0, 11, 3]
	#  Get the size
	n = inorder.length
	tree.make_tree(inorder, n)
	# 
	# 		            12
	# 		          /   \
	# 		         /     \
	# 		        /       \
	# 		       8        11
	# 		      /  \     /  \
	# 		     7    4   9    3
	# 		      \        \    
	# 		       6        0  
	# 		      / \
	# 		     2   1 
	# 		    ----------------  
	# 		    Resultant binary tree
	# 		 
	
	tree.print_tree()
end

main()

Output

 Preorder :   12  8  7  6  2  1  4  11  9  0  3
 Inorder :   7  2  6  1  8  4  12  9  0  11  3
 Postorder :   2  1  6  7  4  8  0  9  3  11  12
//  Scala Program 
//  Construct Special Binary Tree from given Inorder 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
	def construct_tree(inorder: Array[Int], first: Int, last: Int): Node = {
		// return node
		if (first > last)
		{
			return null;
		}
		var location: Int = first;
		var i: Int = first + 1;
		// Find largest element
		while (i <= last)
		{
			if (inorder(i) > inorder(location))
			{
				location = i;
			}
			i += 1;
		}
		var node: Node = new Node(inorder(location));
		// recursively constructing left and right subtree
		node.left = construct_tree(inorder, first, location - 1);
		node.right = construct_tree(inorder, location + 1, last);
		return node;
	}
	// handles the request of construct binary tree
	def make_tree(inorder: Array[Int], n: Int): Unit = {
		if (n <= 0)
		{
			// Invalid sequence
			this.root = null;
		}
		else
		{
			this.root = construct_tree(inorder, 0, n - 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();
		var inorder: Array[Int] = Array(7, 2, 6, 1, 8, 4, 12, 9, 0, 11, 3);
		//  Get the size
		var n: Int = inorder.length;
		tree.make_tree(inorder, n);
		// 
		// 		            12
		// 		          /   \
		// 		         /     \
		// 		        /       \
		// 		       8        11
		// 		      /  \     /  \
		// 		     7    4   9    3
		// 		      \        \    
		// 		       6        0  
		// 		      / \
		// 		     2   1 
		// 		    ----------------  
		// 		    Resultant binary tree
		// 		 
		tree.print_tree();
	}
}

Output

 Preorder :   12  8  7  6  2  1  4  11  9  0  3
 Inorder :   7  2  6  1  8  4  12  9  0  11  3
 Postorder :   2  1  6  7  4  8  0  9  3  11  12
//  Swift 4 Program 
//  Construct Special Binary Tree from given Inorder 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
	func construct_tree(_ inorder: [Int], _ first: Int, _ last: Int)->Node?
	{
		// return node
		if (first > last)
		{
			return nil;
		}
		var location: Int = first;
		var i: Int = first + 1;
		// Find largest element
		while (i <= last)
		{
			if (inorder[i] > inorder[location])
			{
				location = i;
			}
			i += 1;
		}
		let node: Node? = Node(inorder[location]);
		// recursively constructing left and right subtree
		node!.left = self.construct_tree(inorder, first, location - 1);node!.right = self.construct_tree(inorder, location + 1, last);
		return node;
	}
	// handles the request of construct binary tree
	func make_tree(_ inorder: [Int], _ n: Int)
	{
		if (n <= 0)
		{
			// Invalid sequence
			self.root = nil;
		}
		else
		{
			self.root = self.construct_tree(inorder, 0, n - 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();
	let inorder: [Int] = [7, 2, 6, 1, 8, 4, 12, 9, 0, 11, 3];
	//  Get the size
	let n: Int = inorder.count;
	tree.make_tree(inorder, n);
	// 
	// 		            12
	// 		          /   \
	// 		         /     \
	// 		        /       \
	// 		       8        11
	// 		      /  \     /  \
	// 		     7    4   9    3
	// 		      \        \    
	// 		       6        0  
	// 		      / \
	// 		     2   1 
	// 		    ----------------  
	// 		    Resultant binary tree
	// 		 
	tree.print_tree();
}
main();

Output

 Preorder :    12   8   7   6   2   1   4   11   9   0   3
 Inorder :    7   2   6   1   8   4   12   9   0   11   3
 Postorder :    2   1   6   7   4   8   0   9   3   11   12




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