Skip to main content

Construct tree from given string parenthesis expression

Here given code implementation process.

/*
    C Program 
    Construct tree from given string parenthesis expression 
*/
#include <stdio.h>
#include <stdlib.h>

//Binary Tree node
struct Node
{
	int data;
	struct Node *left, *right;
};

struct MyStack
{
	struct Node *element;
	int indicator;
	struct MyStack *next;
};
//Create a MyStack element and return this reference
struct MyStack *push(struct Node *tree_node, struct MyStack **top, int indicator)
{
	struct MyStack *node = (struct MyStack *) malloc(sizeof(struct MyStack));
	if (node != NULL)
	{
		//set pointer values
		node->element = tree_node;
		node->next = *top;
		node->indicator = indicator;*top = node;
	}
	else
	{
		printf("Memory Overflow\n");
	}
	return node;
}
//Remove a top node of stack
void pop(struct MyStack **top)
{
	if ( *top != NULL)
	{
		struct MyStack *remove = *top;
        *top = remove->next;
		remove->element = NULL;
		remove->next = NULL;
		//free the allocated memory of node
		free(remove);
		remove = NULL;
	}
}
//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 string 
// 1) expression can be contains positive number example (1,44,2324,55 etc)
// 2) Expression contains parentheses which is indicates is left and right child
//  Example 1 : () null child, other (4) child with node 4 
struct Node *construct_tree(char str[], int n)
{
	// Define loop controlling variables
	int j = 0;
	int i = 0;
	// Define stack variable
	struct MyStack *top = NULL;
	// Define some useful Tree node variables
	struct Node *auxiliary = NULL;
	struct Node *temp = NULL;
	struct Node *child = NULL, *parent = NULL;
	// Define some auxiliary variables
	int num = 0;
	int position = 0;
	//Display given expression
	printf("\n Expression : %s\n", str);
	//Construct tree
	while (i < n)
	{
		if (str[i] == '(')
		{
			// Add null node
			temp = NULL;
			push(temp, &top, 0);
			i++;
		}
		else if (str[i] == ')')
		{
			position = 0;
			// Reset the value of parent and child node
			child = NULL;
			parent = NULL;
			if (top != NULL)
			{
				//Get child node
				child = top->element;
				pop( &top);
			}
			if (top != NULL)
			{
				//Get parent node
				parent = top->element;
				position = top->indicator;
				pop(&top);
			}
			if (parent != NULL)
			{
				//connect parent to child node
				if (position == 0)
				{
					// Add node in left side
					parent->left = child;
					position = 1;
				}
				else if (position == 1)
				{
					// Add node in right side
					parent->right = child;
					position = 2;
				}
				else
				{
					// Tree exist More than 2 child nodes
					// example  x(1)(2)(3) x is parent
					printf("\n More than 2 child of node %d\n", parent->data);
					return NULL;
				}
				push(parent, &top, position);
			}
			i++;
		}
		else if (str[i] >= '1' && str[i] <= '9')
		{
			num = 0;
			// Collect node value
			while (i < n && str[i] != '(' && str[i] != ')')
			{
				num = (num *10) + (str[i] - '0');
				i++;
			}
			// Get new tree node
			temp = get_node(num);
			if (top != NULL)
			{
				auxiliary = top->element;
				if (auxiliary == NULL)
				{
					// When stack top node element is empty then add new node to this location
					top->element = temp;
				}
				else
				{
					// Add new node in tree
					push(temp, &top, 0);
				}
			}
			else
			{
				// When stack is empty, then add first node
				push(temp, &top, 0);
			}
		}
		else
		{
			// When not a valid expression
			printf("\n Invalid Expression \n");
			return NULL;
		}
	}
	if (top != NULL)
	{
		auxiliary = top->element;
		pop(&top);
		return auxiliary;
	}
	else
	{
		return NULL;
	}
}
//handles the request of construct binary tree
struct Node *make_tree(char str[], int n)
{
	if (n <= 0)
	{
		//Invalid sequence
		return NULL;
	}
	else
	{
		return construct_tree(str, n);
	}
}
//Handles the request of display the element of tree 
void print_tree(struct Node *root)
{
	if (root == NULL)
	{
		return;
	}
	// Display tree elements in three formats
	printf("\n Preorder : ");
	print_preorder(root);
	printf("\n Inorder : ");
	print_inorder(root);
	printf("\n Postorder : ");
	print_postorder(root);
	printf("\n");
}
int main()
{
	// string expression
	char str[] = "16(7(4()(6))(2))(8(9()(1))(3(15)))";
	// Get the size
	int size = sizeof(str) / sizeof(str[0]) - 1;
	struct Node *root = make_tree(str, size);
	/*
	        16
	      /    \
	     /      \
	    /        \
	   7         8
	  /  \     /   \
	 4    2   9     3
	  \        \   /  
	   6        1 15  
	----------------  
	Resultant binary tree
	*/
	print_tree(root);
	return 0;
}

Output

 Expression : 16(7(4()(6))(2))(8(9()(1))(3(15)))

 Preorder :   16  7  4  6  2  8  9  1  3  15
 Inorder :   4  6  7  2  16  9  1  8  15  3
 Postorder :   6  4  2  7  1  9  15  3  8  16
/*
    Java Program 
    Construct tree from given string parenthesis expression 
*/

// 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;
    }
}
//Stack Node
class StackNode
{
    public Node element;
    public StackNode next;
    public int indicator;
    public StackNode(Node element, int indicator)
    {
        this.element = element;
        this.next = null;
        this.indicator = indicator;
    }
}
//Define custom stack and its operation
class MyStack
{
    public StackNode top;
    public int length;

    public MyStack()
    {
        this.top = null;
        this.length = 0;

    }
    //Add a new element in stack
    public void push(Node element, int indicator)
    {
        //Make a new stack node
        StackNode new_node = new StackNode(element,indicator);
        if (new_node != null)
        {
            new_node.next = this.top;
            this.top = new_node;
            this.length++;
        }
        else
        {
            System.out.print("Memory overflow\n");
        }
    }
    //remove a top element in stack
    public void pop()
    {
        if (this.top != null)
        {
            this.top = this.top.next;
            this.length--;
        }
    }
    //check that whether stack is empty or not
    public boolean is_empty()
    {
        if (this.top != null)
        {
            return false;
        }
        else
        {
            return true;
        }
    }
    public int is_size()
    {
        return this.length;
    }
    //Used to get top element of stack
    public Node peek()
    {
        if (this.top != null)
        {
            return this.top.element;
        }
        else
        {
            return 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 string 
    // 1) expression can be contains positive number example (1,44,2324,55 etc)
    // 2) Expression contains parentheses which is indicates is left and right child
    //  Example 1 : () null child, other (4) child with node 4 
    public Node construct_tree(String str, int n)
    {
        // Define loop controlling variables
        int j = 0;
        int i = 0;
        // Define stack variable
        MyStack stack = new MyStack();
        // Define some useful Tree node variables
        Node auxiliary = null;
        Node temp = null;
        Node child = null;
        Node parent = null;
        // Define some auxiliary variables
        int num = 0;
        int position = 0;
        //Display given expression
        System.out.print("\n Expression : " + str + "\n");
        //Construct tree
        while (i < n)
        {
            if (str.charAt(i) == '(')
            {
                // Add null node
                temp = null;
                stack.push(temp, 0);
                i++;
            }
            else if (str.charAt(i) == ')')
            {
                if (stack.is_size() < 2)
                {
                    //not a valid parent child relation
                    return null;
                }
                position = 0;
                // Reset the value of parent and child node
                child = null;
                parent = null;
                if (stack.is_empty() == false)
                {
                    //Get child node
                    child = stack.peek();
                    stack.pop();
                }
                if (stack.is_empty() == false)
                {
                    //Get parent node
                    parent = stack.peek();
                    position = stack.top.indicator;
                    stack.pop();
                }
                if (parent != null)
                {
                    //connect parent to child node
                    if (position == 0)
                    {
                        // Add node in left side
                        parent.left = child;
                        position = 1;
                    }
                    else if (position == 1)
                    {
                        // Add node in right side
                        parent.right = child;
                        position = 2;
                    }
                    else
                    {
                        // Tree exist More than 2 child nodes
                        // example  x(1)(2)(3) x is parent
                        System.out.print("\n More than 2 child of node " + parent.data + "\n");
                        return null;
                    }
                    stack.push(parent, position);
                }
                i++;
            }
            else if (str.charAt(i) >= '1' && str.charAt(i) <= '9')
            {
                num = 0;
                // Collect node value
                while (i < n && str.charAt(i) != '(' && str.charAt(i) != ')')
                {
                    num = (num * 10) + (str.charAt(i) - '0');
                    i++;
                }
                // Get new tree node
                temp = new Node(num);
                if (stack.is_empty() == false)
                {
                    auxiliary = stack.peek();
                    if (auxiliary == null)
                    {
                        // When stack top node element is empty then add new node to this location
                        stack.top.element = temp;
                    }
                    else
                    {
                        // Add new node in tree
                        stack.push(temp, 0);
                    }
                }
                else
                {
                    // When stack is empty, then add first node
                    stack.push(temp, 0);
                }
            }
            else
            {
                // When not a valid expression
                System.out.print("\n Invalid Expression \n");
                return null;
            }
        }
        if (stack.is_empty() == false)
        {
            auxiliary = stack.peek();
            stack.pop();
            return auxiliary;
        }
        else
        {
            return null;
        }
    }
    //handles the request of construct binary tree
    public void make_tree(String str, int n)
    {
        if (n <= 0)
        {
            //Invalid sequence
            this.root = null;
        }
        else
        {
            this.root = construct_tree(str, n);
        }
    }
    //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();
        // string expression
        String str = "16(7(4()(6))(2))(8(9()(1))(3(15)))";
        // Get the size
        int size = str.length();
        tree.make_tree(str, size);
        /*
                    16
                  /    \
                 /      \
                /        \
               7         8
              /  \     /   \
             4    2   9     3
              \        \   /  
               6        1 15  
            ----------------  
            Resultant binary tree
            */
        tree.print_tree();
    }
}

Output

 Expression : 16(7(4()(6))(2))(8(9()(1))(3(15)))

 Preorder :   16  7  4  6  2  8  9  1  3  15
 Inorder :   4  6  7  2  16  9  1  8  15  3
 Postorder :   6  4  2  7  1  9  15  3  8  16
// Include header file
#include <iostream>

using namespace std;
// 
//     C++ Program 
//     Construct tree from given string parenthesis expression 
//  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;
	}
};
// Stack Node
class StackNode
{
	public: Node *element;
	StackNode *next;
	int indicator;
	StackNode(Node *element, int indicator)
	{
		this->element = element;
		this->next = NULL;
		this->indicator = indicator;
	}
};
// Define custom stack and its operation
class MyStack
{
	public: StackNode *top;
	int length;
	MyStack()
	{
		this->top = NULL;
		this->length = 0;
	}
	// Add a new element in stack
	void push(Node *element, int indicator)
	{
		// Make a new stack node
		StackNode *new_node = new StackNode(element, indicator);
		if (new_node != NULL)
		{
			new_node->next = this->top;
			this->top = new_node;
			this->length++;
		}
		else
		{
			cout << "Memory overflow\n";
		}
	}
	// remove a top element in stack
	void pop()
	{
		if (this->top != NULL)
		{
			this->top = this->top->next;
			this->length--;
		}
	}
	// check that whether stack is empty or not
	bool is_empty()
	{
		if (this->top != NULL)
		{
			return false;
		}
		else
		{
			return true;
		}
	}
	int is_size()
	{
		return this->length;
	}
	// Used to get top element of stack
	Node *peek()
	{
		if (this->top != NULL)
		{
			return this->top->element;
		}
		else
		{
			return 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 string
	//  1) expression can be contains positive number example (1,44,2324,55 etc)
	//  2) Expression contains parentheses which is indicates is left and right child
	//   Example 1 : () null child, other (4) child with node 4
	Node *construct_tree(string str, int n)
	{
		//  Define loop controlling variables
		int j = 0;
		int i = 0;
		//  Define stack variable
		MyStack stack = MyStack();
		//  Define some useful Tree node variables
		Node *auxiliary = NULL;
		Node *temp = NULL;
		Node *child = NULL;
		Node *parent = NULL;
		//  Define some auxiliary variables
		int num = 0;
		int position = 0;
		// Display given expression
		cout << "\n Expression : " << str << "\n";
		// Construct tree
		while (i < n)
		{
			if (str[i] == '(')
			{
				//  Add null node
				temp = NULL;
				stack.push(temp, 0);
				i++;
			}
			else if (str[i] == ')')
			{
				if (stack.is_size() < 2)
				{
					// not a valid parent child relation
					return NULL;
				}
				position = 0;
				//  Reset the value of parent and child node
				child = NULL;
				parent = NULL;
				if (stack.is_empty() == false)
				{
					// Get child node
					child = stack.peek();
					stack.pop();
				}
				if (stack.is_empty() == false)
				{
					// Get parent node
					parent = stack.peek();
					position = stack.top->indicator;
					stack.pop();
				}
				if (parent != NULL)
				{
					// connect parent to child node
					if (position == 0)
					{
						//  Add node in left side
						parent->left = child;
						position = 1;
					}
					else if (position == 1)
					{
						//  Add node in right side
						parent->right = child;
						position = 2;
					}
					else
					{
						//  Tree exist More than 2 child nodes
						//  example  x(1)(2)(3) x is parent
						cout << "\n More than 2 child of node " << parent->data << "\n";
						return NULL;
					}
					stack.push(parent, position);
				}
				i++;
			}
			else if (str[i] >= '1' && str[i] <= '9')
			{
				num = 0;
				//  Collect node value
				while (i < n && str[i] != '(' && str[i] != ')')
				{
					num = (num *10) + (str[i] - '0');
					i++;
				}
				//  Get new tree node
				temp = new Node(num);
				if (stack.is_empty() == false)
				{
					auxiliary = stack.peek();
					if (auxiliary == NULL)
					{
						//  When stack top node element is empty then add new node to this location
						stack.top->element = temp;
					}
					else
					{
						//  Add new node in tree
						stack.push(temp, 0);
					}
				}
				else
				{
					//  When stack is empty, then add first node
					stack.push(temp, 0);
				}
			}
			else
			{
				//  When not a valid expression
				cout << "\n Invalid Expression \n";
				return NULL;
			}
		}
		if (stack.is_empty() == false)
		{
			auxiliary = stack.peek();
			stack.pop();
			return auxiliary;
		}
		else
		{
			return NULL;
		}
	}
	// handles the request of construct binary tree
	void make_tree(string str, int n)
	{
		if (n <= 0)
		{
			// Invalid sequence
			this->root = NULL;
		}
		else
		{
			this->root = this->construct_tree(str, n);
		}
	}
	// 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();
	//  string expression
	string str = "16(7(4()(6))(2))(8(9()(1))(3(15)))";
	//  Get the size
	int size = str.length();
	tree.make_tree(str, size);
	// 
	// 		            16
	// 		          /    \
	// 		         /      \
	// 		        /        \
	// 		       7         8
	// 		      /  \     /   \
	// 		     4    2   9     3
	// 		      \        \   /  
	// 		       6        1 15  
	// 		    ----------------  
	// 		    Resultant binary tree
	// 		    
	tree.print_tree();
	return 0;
}

Output

 Expression : 16(7(4()(6))(2))(8(9()(1))(3(15)))

 Preorder :   16  7  4  6  2  8  9  1  3  15
 Inorder :   4  6  7  2  16  9  1  8  15  3
 Postorder :   6  4  2  7  1  9  15  3  8  16
// Include namespace system
using System;

// C# Program 
// Construct tree from given string parenthesis expression 

//  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;
	}
}
// Stack Node
public class StackNode
{
	public Node element;
	public StackNode next;
	public int indicator;
	public StackNode(Node element, int indicator)
	{
		this.element = element;
		this.next = null;
		this.indicator = indicator;
	}
}
// Define custom stack and its operation
public class MyStack
{
	public StackNode top;
	public int length;
	public MyStack()
	{
		this.top = null;
		this.length = 0;
	}
	// Add a new element in stack
	public void push(Node element, int indicator)
	{
		// Make a new stack node
		StackNode new_node = new StackNode(element, indicator);
		if (new_node != null)
		{
			new_node.next = this.top;
			this.top = new_node;
			this.length++;
		}
		else
		{
			Console.Write("Memory overflow\n");
		}
	}
	// remove a top element in stack
	public void pop()
	{
		if (this.top != null)
		{
			this.top = this.top.next;
			this.length--;
		}
	}
	// check that whether stack is empty or not
	public Boolean is_empty()
	{
		if (this.top != null)
		{
			return false;
		}
		else
		{
			return true;
		}
	}
	public int is_size()
	{
		return this.length;
	}
	// Used to get top element of stack
	public Node peek()
	{
		if (this.top != null)
		{
			return this.top.element;
		}
		else
		{
			return 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 string
	//  1) expression can be contains positive number example (1,44,2324,55 etc)
	//  2) Expression contains parentheses which is indicates is left and right child
	//   Example 1 : () null child, other (4) child with node 4
	public Node construct_tree(String str, int n)
	{
		//  Define loop controlling variables
		int i = 0;
		//  Define stack variable
		MyStack stack = new MyStack();
		//  Define some useful Tree node variables
		Node auxiliary = null;
		Node temp = null;
		Node child = null;
		Node parent = null;
		//  Define some auxiliary variables
		int num = 0;
		int position = 0;
		// Display given expression
		Console.Write("\n Expression : " + str + "\n");
		// Construct tree
		while (i < n)
		{
			if (str[i] == '(')
			{
				//  Add null node
				temp = null;
				stack.push(temp, 0);
				i++;
			}
			else if (str[i] == ')')
			{
				if (stack.is_size() < 2)
				{
					// not a valid parent child relation
					return null;
				}
				position = 0;
				//  Reset the value of parent and child node
				child = null;
				parent = null;
				if (stack.is_empty() == false)
				{
					// Get child node
					child = stack.peek();
					stack.pop();
				}
				if (stack.is_empty() == false)
				{
					// Get parent node
					parent = stack.peek();
					position = stack.top.indicator;
					stack.pop();
				}
				if (parent != null)
				{
					// connect parent to child node
					if (position == 0)
					{
						//  Add node in left side
						parent.left = child;
						position = 1;
					}
					else if (position == 1)
					{
						//  Add node in right side
						parent.right = child;
						position = 2;
					}
					else
					{
						//  Tree exist More than 2 child nodes
						//  example  x(1)(2)(3) x is parent
						Console.Write("\n More than 2 child of node " + parent.data + "\n");
						return null;
					}
					stack.push(parent, position);
				}
				i++;
			}
			else if (str[i] >= '1' && str[i] <= '9')
			{
				num = 0;
				//  Collect node value
				while (i < n && str[i] != '(' && str[i] != ')')
				{
					num = (num * 10) + (str[i] - '0');
					i++;
				}
				//  Get new tree node
				temp = new Node(num);
				if (stack.is_empty() == false)
				{
					auxiliary = stack.peek();
					if (auxiliary == null)
					{
						//  When stack top node element is empty then add new node to this location
						stack.top.element = temp;
					}
					else
					{
						//  Add new node in tree
						stack.push(temp, 0);
					}
				}
				else
				{
					//  When stack is empty, then add first node
					stack.push(temp, 0);
				}
			}
			else
			{
				//  When not a valid expression
				Console.Write("\n Invalid Expression \n");
				return null;
			}
		}
		if (stack.is_empty() == false)
		{
			auxiliary = stack.peek();
			stack.pop();
			return auxiliary;
		}
		else
		{
			return null;
		}
	}
	// handles the request of construct binary tree
	public void make_tree(String str, int n)
	{
		if (n <= 0)
		{
			// Invalid sequence
			this.root = null;
		}
		else
		{
			this.root = construct_tree(str, n);
		}
	}
	// 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();
		//  string expression
		String str = "16(7(4()(6))(2))(8(9()(1))(3(15)))";
		//  Get the size
		int size = str.Length;
		tree.make_tree(str, size);
		// 
		// 		            16
		// 		          /    \
		// 		         /      \
		// 		        /        \
		// 		       7         8
		// 		      /  \     /   \
		// 		     4    2   9     3
		// 		      \        \   /  
		// 		       6        1 15  
		// 		    ----------------  
		// 		    Resultant binary tree
		// 		    
		tree.print_tree();
	}
}

Output

 Expression : 16(7(4()(6))(2))(8(9()(1))(3(15)))

 Preorder :   16  7  4  6  2  8  9  1  3  15
 Inorder :   4  6  7  2  16  9  1  8  15  3
 Postorder :   6  4  2  7  1  9  15  3  8  16
<?php

//  Php Program 
//  Construct tree from given string parenthesis expression 

//  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;
	}
}
// Stack Node
class StackNode
{
	public $element;
	public $next;
	public $indicator;

	function __construct($element, $indicator)
	{
		$this->element = $element;
		$this->next = null;
		$this->indicator = $indicator;
	}
}
// Define custom stack and its operation
class MyStack
{
	public $top;
	public $length;

	function __construct()
	{
		$this->top = null;
		$this->length = 0;
	}
	// Add a new element in stack
	public	function push($element, $indicator)
	{
		// Make a new stack node
		$new_node = new StackNode($element, $indicator);
		if ($new_node != null)
		{
			$new_node->next = $this->top;
			$this->top = $new_node;
			$this->length++;
		}
		else
		{
			echo "Memory overflow\n";
		}
	}
	// remove a top element in stack
	public	function pop()
	{
		if ($this->top != null)
		{
			$this->top = $this->top->next;
			$this->length--;
		}
	}
	// check that whether stack is empty or not
	public	function is_empty()
	{
		if ($this->top != null)
		{
			return false;
		}
		else
		{
			return true;
		}
	}
	public	function is_size()
	{
		return $this->length;
	}
	// Used to get top element of stack
	public	function peek()
	{
		if ($this->top != null)
		{
			return $this->top->element;
		}
		else
		{
			return 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 string
	//  1) expression can be contains positive number example (1,44,2324,55 etc)
	//  2) Expression contains parentheses which is indicates is left and right child
	//   Example 1 : () null child, other (4) child with node 4
	public	function construct_tree($str, $n)
	{
		//  Define loop controlling variable
		$i = 0;
		//  Define stack variable
		$stack = new MyStack();
		//  Define some useful Tree node variables
		$auxiliary = null;
		$temp = null;
		$child = null;
		$parent = null;
		//  Define some auxiliary variables
		$num = 0;
		$position = 0;
		// Display given expression
		echo "\n Expression : ". $str ."\n";
		// Construct tree
		while ($i < $n)
		{
			if ($str[$i] == '(')
			{
				//  Add null node
				$temp = null;
				$stack->push($temp, 0);
				$i++;
			}
			else if ($str[$i] == ')')
			{
				if ($stack->is_size() < 2)
				{
					// not a valid parent child relation
					return null;
				}
				$position = 0;
				//  Reset the value of parent and child node
				$child = null;
				$parent = null;
				if ($stack->is_empty() == false)
				{
					// Get child node
					$child = $stack->peek();
					$stack->pop();
				}
				if ($stack->is_empty() == false)
				{
					// Get parent node
					$parent = $stack->peek();
					$position = $stack->top->indicator;
					$stack->pop();
				}
				if ($parent != null)
				{
					// connect parent to child node
					if ($position == 0)
					{
						//  Add node in left side
						$parent->left = $child;
						$position = 1;
					}
					else if ($position == 1)
					{
						//  Add node in right side
						$parent->right = $child;
						$position = 2;
					}
					else
					{
						//  Tree exist More than 2 child nodes
						//  example  x(1)(2)(3) x is parent
						echo "\n More than 2 child of node ". $parent->data ."\n";
						return null;
					}
					$stack->push($parent, $position);
				}
				$i++;
			}
			else if (ord($str[$i]) >= ord('1') && ord($str[$i]) <= ord('9'))
			{
				$num = 0;
				//  Collect node value
				while ($i < $n && $str[$i] != '(' && $str[$i] != ')')
				{
					$num = ($num * 10) + (ord($str[$i]) - ord('0'));
					$i++;
				}
				//  Get new tree node
				$temp = new Node($num);
				if ($stack->is_empty() == false)
				{
					$auxiliary = $stack->peek();
					if ($auxiliary == null)
					{
						//  When stack top node element is empty then add new node to this location
						$stack->top->element = $temp;
					}
					else
					{
						//  Add new node in tree
						$stack->push($temp, 0);
					}
				}
				else
				{
					//  When stack is empty, then add first node
					$stack->push($temp, 0);
				}
			}
			else
			{
				//  When not a valid expression
				echo "\n Invalid Expression \n";
				return null;
			}
		}
		if ($stack->is_empty() == false)
		{
			$auxiliary = $stack->peek();
			$stack->pop();
			return $auxiliary;
		}
		else
		{
			return null;
		}
	}
	// handles the request of construct binary tree
	public	function make_tree($str, $n)
	{
		if ($n <= 0)
		{
			// Invalid sequence
			$this->root = null;
		}
		else
		{
			$this->root = $this->construct_tree($str, $n);
		}
	}
	// 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();
	//  string expression
	$str = "16(7(4()(6))(2))(8(9()(1))(3(15)))";
	//  Get the size
	$size = strlen($str);
	$tree->make_tree($str, $size);
	// 
	// 		            16
	// 		          /    \
	// 		         /      \
	// 		        /        \
	// 		       7         8
	// 		      /  \     /   \
	// 		     4    2   9     3
	// 		      \        \   /  
	// 		       6        1 15  
	// 		    ----------------  
	// 		    Resultant binary tree
	// 		    
	$tree->print_tree();
}
main();

Output

 Expression : 16(7(4()(6))(2))(8(9()(1))(3(15)))

 Preorder :   16  7  4  6  2  8  9  1  3  15
 Inorder :   4  6  7  2  16  9  1  8  15  3
 Postorder :   6  4  2  7  1  9  15  3  8  16
//  Node Js Program 
//  Construct tree from given string parenthesis expression 

//  Binary Tree node
class Node
{
	constructor(data)
	{
		//  Set node value
		this.data = data;
		this.left = null;
		this.right = null;
	}
}
// Stack Node
class StackNode
{
	constructor(element, indicator)
	{
		this.element = element;
		this.next = null;
		this.indicator = indicator;
	}
}
// Define custom stack and its operation
class MyStack
{
	constructor()
	{
		this.top = null;
		this.length = 0;
	}
	// Add a new element in stack
	push(element, indicator)
	{
		// Make a new stack node
		var new_node = new StackNode(element, indicator);
		if (new_node != null)
		{
			new_node.next = this.top;
			this.top = new_node;
			this.length++;
		}
		else
		{
			process.stdout.write("Memory overflow\n");
		}
	}
	// remove a top element in stack
	pop()
	{
		if (this.top != null)
		{
			this.top = this.top.next;
			this.length--;
		}
	}
	// check that whether stack is empty or not
	is_empty()
	{
		if (this.top != null)
		{
			return false;
		}
		else
		{
			return true;
		}
	}
	is_size()
	{
		return this.length;
	}
	// Used to get top element of stack
	peek()
	{
		if (this.top != null)
		{
			return this.top.element;
		}
		else
		{
			return 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 string
	//  1) expression can be contains positive number example (1,44,2324,55 etc)
	//  2) Expression contains parentheses which is indicates is left and right child
	//   Example 1 : () null child, other (4) child with node 4
	construct_tree(str, n)
	{
		//  Define loop controlling variable
		var i = 0;
		//  Define stack variable
		var stack = new MyStack();
		//  Define some useful Tree node variables
		var auxiliary = null;
		var temp = null;
		var child = null;
		var parent = null;
		//  Define some auxiliary variables
		var num = 0;
		var position = 0;
		// Display given expression
		process.stdout.write("\n Expression : " + str + "\n");
		// Construct tree
		while (i < n)
		{
			if (str[i] == '(')
			{
				//  Add null node
				temp = null;
				stack.push(temp, 0);
				i++;
			}
			else if (str[i] == ')')
			{
				if (stack.is_size() < 2)
				{
					// not a valid parent child relation
					return null;
				}
				position = 0;
				//  Reset the value of parent and child node
				child = null;
				parent = null;
				if (stack.is_empty() == false)
				{
					// Get child node
					child = stack.peek();
					stack.pop();
				}
				if (stack.is_empty() == false)
				{
					// Get parent node
					parent = stack.peek();
					position = stack.top.indicator;
					stack.pop();
				}
				if (parent != null)
				{
					// connect parent to child node
					if (position == 0)
					{
						//  Add node in left side
						parent.left = child;
						position = 1;
					}
					else if (position == 1)
					{
						//  Add node in right side
						parent.right = child;
						position = 2;
					}
					else
					{
						//  Tree exist More than 2 child nodes
						//  example  x(1)(2)(3) x is parent
						process.stdout.write("\n More than 2 child of node " + parent.data + "\n");
						return null;
					}
					stack.push(parent, position);
				}
				i++;
			}
			else if ((str[i]).charCodeAt(0) >= ('1').charCodeAt(0) && (str[i]).charCodeAt(0) <= ('9').charCodeAt(0))
			{
				num = 0;
				//  Collect node value
				while (i < n && str[i] != '(' && str[i] != ')')
				{
					num = (num * 10) + ((str[i]).charCodeAt(0) - ('0').charCodeAt(0));
					i++;
				}
				//  Get new tree node
				temp = new Node(num);
				if (stack.is_empty() == false)
				{
					auxiliary = stack.peek();
					if (auxiliary == null)
					{
						//  When stack top node element is empty then add new node to this location
						stack.top.element = temp;
					}
					else
					{
						//  Add new node in tree
						stack.push(temp, 0);
					}
				}
				else
				{
					//  When stack is empty, then add first node
					stack.push(temp, 0);
				}
			}
			else
			{
				//  When not a valid expression
				process.stdout.write("\n Invalid Expression \n");
				return null;
			}
		}
		if (stack.is_empty() == false)
		{
			auxiliary = stack.peek();
			stack.pop();
			return auxiliary;
		}
		else
		{
			return null;
		}
	}
	// handles the request of construct binary tree
	make_tree(str, n)
	{
		if (n <= 0)
		{
			// Invalid sequence
			this.root = null;
		}
		else
		{
			this.root = this.construct_tree(str, n);
		}
	}
	// 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();
	//  string expression
	var str = "16(7(4()(6))(2))(8(9()(1))(3(15)))";
	//  Get the size
	var size = str.length;
	tree.make_tree(str, size);
	// 
	// 		            16
	// 		          /    \
	// 		         /      \
	// 		        /        \
	// 		       7         8
	// 		      /  \     /   \
	// 		     4    2   9     3
	// 		      \        \   /  
	// 		       6        1 15  
	// 		    ----------------  
	// 		    Resultant binary tree
	// 		    
	tree.print_tree();
}
main();

Output

 Expression : 16(7(4()(6))(2))(8(9()(1))(3(15)))

 Preorder :   16  7  4  6  2  8  9  1  3  15
 Inorder :   4  6  7  2  16  9  1  8  15  3
 Postorder :   6  4  2  7  1  9  15  3  8  16
#     Python 3 Program 
#     Construct tree from given string parenthesis expression 

#  Binary Tree node
class Node :
	
	def __init__(self, data) :
		#  Set node value
		self.data = data
		self.left = None
		self.right = None
	

# Stack Node
class StackNode :
	
	def __init__(self, element, indicator) :
		self.element = element
		self.next = None
		self.indicator = indicator
	

# Define custom stack and its operation
class MyStack :
	
	def __init__(self) :
		self.top = None
		self.length = 0
	
	# Add a new element in stack
	def push(self, element, indicator) :
		# Make a new stack node
		new_node = StackNode(element, indicator)
		if (new_node != None) :
			new_node.next = self.top
			self.top = new_node
			self.length += 1
		else :
			print("Memory overflow\n", end = "")
		
	
	# remove a top element in stack
	def pop(self) :
		if (self.top != None) :
			self.top = self.top.next
			self.length -= 1
		
	
	# check that whether stack is empty or not
	def is_empty(self) :
		if (self.top != None) :
			return False
		else :
			return True
		
	
	def is_size(self) :
		return self.length
	
	# Used to get top element of stack
	def peek(self) :
		if (self.top != None) :
			return self.top.element
		else :
			return 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 string 
	#  1) expression can be contains positive number example (1,44,2324,55 etc)
	#  2) Expression contains parentheses which is indicates is left and right child
	#   Example 1 : () null child, other (4) child with node 4 
	def construct_tree(self, str, n) :
		#  Define loop controlling variable
		i = 0
		#  Define stack variable
		stack = MyStack()
		#  Define some useful Tree node variables
		auxiliary = None
		temp = None
		child = None
		parent = None
		#  Define some auxiliary variables
		num = 0
		position = 0
		# Display given expression
		print("\n Expression : ", str )
		# Construct tree
		while (i < n) :
			if (str[i] == '(') :
				#  Add null node
				temp = None
				stack.push(temp, 0)
				i += 1
			
			elif(str[i] == ')') :
				if (stack.is_size() < 2) :
					# not a valid parent child relation
					return None
				
				position = 0
				#  Reset the value of parent and child node
				child = None
				parent = None
				if (stack.is_empty() == False) :
					# Get child node
					child = stack.peek()
					stack.pop()
				
				if (stack.is_empty() == False) :
					# Get parent node
					parent = stack.peek()
					position = stack.top.indicator
					stack.pop()
				
				if (parent != None) :
					# connect parent to child node
					if (position == 0) :
						#  Add node in left side
						parent.left = child
						position = 1
					
					elif(position == 1) :
						#  Add node in right side
						parent.right = child
						position = 2
					else :
						#  Tree exist More than 2 child nodes
						#  example  x(1)(2)(3) x is parent
						print("\n More than 2 child of node ", parent.data )
						return None
					
					stack.push(parent, position)
				
				i += 1
			
			elif(ord(str[i]) >= ord('1') and ord(str[i]) <= ord('9')) :
				num = 0
				#  Collect node value
				while (i < n and str[i] != '('
					and str[i] != ')') :
					num = (num * 10) + (ord(str[i]) - ord('0'))
					i += 1
				
				#  Get new tree node
				temp = Node(num)
				if (stack.is_empty() == False) :
					auxiliary = stack.peek()
					if (auxiliary == None) :
						#  When stack top node element is empty then add new node to this location
						stack.top.element = temp
					else :
						#  Add new node in tree
						stack.push(temp, 0)
					
				else :
					#  When stack is empty, then add first node
					stack.push(temp, 0)
				
			else :
				#  When not a valid expression
				print("\n Invalid Expression \n", end = "")
				return None
			
		
		if (stack.is_empty() == False) :
			auxiliary = stack.peek()
			stack.pop()
			return auxiliary
		else :
			return None
		
	
	# handles the request of construct binary tree
	def make_tree(self, str, n) :
		if (n <= 0) :
			# Invalid sequence
			self.root = None
		else :
			self.root = self.construct_tree(str, n)
		
	
	# 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()
	#  string expression
	str = "16(7(4()(6))(2))(8(9()(1))(3(15)))"
	#  Get the size
	size = len(str)
	tree.make_tree(str, size)
	# 
	# 		            16
	# 		          /    \
	# 		         /      \
	# 		        /        \
	# 		       7         8
	# 		      /  \     /   \
	# 		     4    2   9     3
	# 		      \        \   /  
	# 		       6        1 15  
	# 		    ----------------  
	# 		    Resultant binary tree
	# 		    
	
	tree.print_tree()

if __name__ == "__main__": main()

Output

 Expression :  16(7(4()(6))(2))(8(9()(1))(3(15)))

 Preorder :    16   7   4   6   2   8   9   1   3   15
 Inorder :    4   6   7   2   16   9   1   8   15   3
 Postorder :    6   4   2   7   1   9   15   3   8   16
#     Ruby Program 
#     Construct tree from given string parenthesis expression 

#  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

# Stack Node
class StackNode  
	# Define the accessor and reader of class StackNode  
	attr_reader :element, :next, :indicator
	attr_accessor :element, :next, :indicator
 
	
	def initialize(element, indicator) 
		self.element = element
		self.next = nil
		self.indicator = indicator
	end

end

# Define custom stack and its operation
class MyStack  
	# Define the accessor and reader of class MyStack  
	attr_reader :top, :length
	attr_accessor :top, :length
 
	
	def initialize() 
		self.top = nil
		self.length = 0
	end

	# Add a new element in stack
	def push(element, indicator) 
		# Make a new stack node
		new_node = StackNode.new(element, indicator)
		if (new_node != nil) 
			new_node.next = self.top
			self.top = new_node
			self.length += 1
		else 
			print("Memory overflow\n")
		end

	end

	# remove a top element in stack
	def pop() 
		if (self.top != nil) 
			self.top = self.top.next
			self.length -= 1
		end

	end

	# check that whether stack is empty or not
	def is_empty() 
		if (self.top != nil) 
			return false
		else 
			return true
		end

	end

	def is_size() 
		return self.length
	end

	# Used to get top element of stack
	def peek() 
		if (self.top != nil) 
			return self.top.element
		else 
			return nil
		end

	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 string 
	#  1) expression can be contains positive number example (1,44,2324,55 etc)
	#  2) Expression contains parentheses which is indicates is left and right child
	#   Example 1 : () null child, other (4) child with node 4 
	def construct_tree(str, n) 
		#  Define loop controlling variable
		i = 0
		#  Define stack variable
		stack = MyStack.new()
		#  Define some useful Tree node variables
		auxiliary = nil
		temp = nil
		child = nil
		parent = nil
		#  Define some auxiliary variables
		num = 0
		position = 0
		# Display given expression
		print("\n Expression : ", str ,"\n")
		# Construct tree
		while (i < n) 
			if (str[i] == '(') 
				#  Add null node
				temp = nil
				stack.push(temp, 0)
				i += 1
			elsif(str[i] == ')') 
				if (stack.is_size() < 2) 
					# not a valid parent child relation
					return nil
				end

				position = 0
				#  Reset the value of parent and child node
				child = nil
				parent = nil
				if (stack.is_empty() == false) 
					# Get child node
					child = stack.peek()
					stack.pop()
				end

				if (stack.is_empty() == false) 
					# Get parent node
					parent = stack.peek()
					position = stack.top.indicator
					stack.pop()
				end

				if (parent != nil) 
					# connect parent to child node
					if (position == 0) 
						#  Add node in left side
						parent.left = child
						position = 1
					elsif(position == 1) 
						#  Add node in right side
						parent.right = child
						position = 2
					else 
						#  Tree exist More than 2 child nodes
						#  example  x(1)(2)(3) x is parent
						print("\n More than 2 child of node ", parent.data ,"\n")
						return nil
					end

					stack.push(parent, position)
				end

				i += 1
			elsif((str[i]).ord >= ('1').ord && (str[i]).ord <= ('9').ord) 
				num = 0
				#  Collect node value
				while (i < n && str[i] != '(' && str[i] != ')') 
					num = (num * 10) + ((str[i]).ord - ('0').ord)
					i += 1
				end

				#  Get new tree node
				temp = Node.new(num)
				if (stack.is_empty() == false) 
					auxiliary = stack.peek()
					if (auxiliary == nil) 
						#  When stack top node element is empty then add new node to this location
						stack.top.element = temp
					else 
						#  Add new node in tree
						stack.push(temp, 0)
					end

				else 
					#  When stack is empty, then add first node
					stack.push(temp, 0)
				end

			else 
				#  When not a valid expression
				print("\n Invalid Expression \n")
				return nil
			end

		end

		if (stack.is_empty() == false) 
			auxiliary = stack.peek()
			stack.pop()
			return auxiliary
		else 
			return nil
		end

	end

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

main()

Output

 Expression : 16(7(4()(6))(2))(8(9()(1))(3(15)))

 Preorder :   16  7  4  6  2  8  9  1  3  15
 Inorder :   4  6  7  2  16  9  1  8  15  3
 Postorder :   6  4  2  7  1  9  15  3  8  16
//  Scala Program 
//  Construct tree from given string parenthesis expression 

//  Binary Tree node
class Node(var data: Int , var left: Node , var right: Node)
{
	def this(data: Int)
	{
		this(data, null, null);
	}
}
// Stack Node
class StackNode(var element: Node , var next: StackNode , var indicator: Int)
{
	def this(element: Node, indicator: Int)
	{
		this(element, null, indicator);
	}
}
// Define custom stack and its operation
class MyStack(var top: StackNode , var length: Int)
{
	def this()
	{
		this(null, 0);
	}
	// Add a new element in stack
	def push(element: Node, indicator: Int): Unit = {
		// Make a new stack node
		var new_node: StackNode = new StackNode(element, indicator);
		if (new_node != null)
		{
			new_node.next = this.top;
			this.top = new_node;
			this.length += 1;
		}
		else
		{
			print("Memory overflow\n");
		}
	}
	// remove a top element in stack
	def pop(): Unit = {
		if (this.top != null)
		{
			this.top = this.top.next;
			this.length -= 1;
		}
	}
	// check that whether stack is empty or not
	def is_empty(): Boolean = {
		if (this.top != null)
		{
			return false;
		}
		else
		{
			return true;
		}
	}
	def is_size(): Int = {
		return this.length;
	}
	// Used to get top element of stack
	def peek(): Node = {
		if (this.top != null)
		{
			return this.top.element;
		}
		else
		{
			return 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 string
	//  1) expression can be contains positive number example (1,44,2324,55 etc)
	//  2) Expression contains parentheses which is indicates is left and right child
	//   Example 1 : () null child, other (4) child with node 4
	def construct_tree(str: String, n: Int): Node = {
		//  Define loop controlling variable
		var i: Int = 0;
		//  Define stack variable
		var stack: MyStack = new MyStack();
		//  Define some useful Tree node variables
		var auxiliary: Node = null;
		var temp: Node = null;
		var child: Node = null;
		var parent: Node = null;
		//  Define some auxiliary variables
		var num: Int = 0;
		var position: Int = 0;
		// Display given expression
		print("\n Expression : " + str + "\n");
		// Construct tree
		while (i < n)
		{
			if (str(i) == '(')
			{
				//  Add null node
				temp = null;
				stack.push(temp, 0);
				i += 1;
			}
			else if (str(i) == ')')
			{
				if (stack.is_size() < 2)
				{
					// not a valid parent child relation
					return null;
				}
				position = 0;
				//  Reset the value of parent and child node
				child = null;
				parent = null;
				if (stack.is_empty() == false)
				{
					// Get child node
					child = stack.peek();
					stack.pop();
				}
				if (stack.is_empty() == false)
				{
					// Get parent node
					parent = stack.peek();
					position = stack.top.indicator;
					stack.pop();
				}
				if (parent != null)
				{
					// connect parent to child node
					if (position == 0)
					{
						//  Add node in left side
						parent.left = child;
						position = 1;
					}
					else if (position == 1)
					{
						//  Add node in right side
						parent.right = child;
						position = 2;
					}
					else
					{
						//  Tree exist More than 2 child nodes
						//  example  x(1)(2)(3) x is parent
						print("\n More than 2 child of node " + parent.data + "\n");
						return null;
					}
					stack.push(parent, position);
				}
				i += 1;
			}
			else if (str(i) >= '1' && str(i) <= '9')
			{
				num = 0;
				//  Collect node value
				while (i < n && str(i) != '(' && str(i) != ')')
				{
					num = (num * 10) + (str(i) - '0');
					i += 1;
				}
				//  Get new tree node
				temp = new Node(num);
				if (stack.is_empty() == false)
				{
					auxiliary = stack.peek();
					if (auxiliary == null)
					{
						//  When stack top node element is empty then add new node to this location
						stack.top.element = temp;
					}
					else
					{
						//  Add new node in tree
						stack.push(temp, 0);
					}
				}
				else
				{
					//  When stack is empty, then add first node
					stack.push(temp, 0);
				}
			}
			else
			{
				//  When not a valid expression
				print("\n Invalid Expression \n");
				return null;
			}
		}
		if (stack.is_empty() == false)
		{
			auxiliary = stack.peek();
			stack.pop();
			return auxiliary;
		}
		else
		{
			return null;
		}
	}
	// handles the request of construct binary tree
	def make_tree(str: String, n: Int): Unit = {
		if (n <= 0)
		{
			// Invalid sequence
			this.root = null;
		}
		else
		{
			this.root = construct_tree(str, n);
		}
	}
	// 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();
		//  string expression
		var str: String = "16(7(4()(6))(2))(8(9()(1))(3(15)))";
		//  Get the size
		var size: Int = str.length();
		tree.make_tree(str, size);
		// 
		// 		            16
		// 		          /    \
		// 		         /      \
		// 		        /        \
		// 		       7         8
		// 		      /  \     /   \
		// 		     4    2   9     3
		// 		      \        \   /  
		// 		       6        1 15  
		// 		    ----------------  
		// 		    Resultant binary tree
		// 		    
		tree.print_tree();
	}
}

Output

 Expression : 16(7(4()(6))(2))(8(9()(1))(3(15)))

 Preorder :   16  7  4  6  2  8  9  1  3  15
 Inorder :   4  6  7  2  16  9  1  8  15  3
 Postorder :   6  4  2  7  1  9  15  3  8  16
//     Swift 4 Program 
//     Construct tree from given string parenthesis expression 

//  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;
	}
}
// Stack Node
class StackNode
{
	var element: Node? ;
	var next: StackNode? ;
	var indicator: Int;
	init(_ element: Node? , _ indicator : Int)
	{
		self.element = element;
		self.next = nil;
		self.indicator = indicator;
	}
}
// Define custom stack and its operation
class MyStack
{
	var top: StackNode? ;
	var length: Int;
	init()
	{
		self.top = nil;
		self.length = 0;
	}
	// Add a new element in stack
	func push(_ element: Node? , _ indicator : Int)
	{
		// Make a new stack node
		let new_node: StackNode? = StackNode(element, indicator);
		if (new_node != nil)
		{
			new_node!.next = self.top;
			self.top = new_node;
			self.length += 1;
		}
		else
		{
			print("Memory overflow\n", terminator: "");
		}
	}
	// remove a top element in stack
	func pop()
	{
		if (self.top != nil)
		{
			self.top = self.top!.next;
			self.length -= 1;
		}
	}
	// check that whether stack is empty or not
	func is_empty()->Bool
	{
		if (self.top != nil)
		{
			return false;
		}
		else
		{
			return true;
		}
	}
	func is_size()->Int
	{
		return self.length;
	}
	// Used to get top element of stack
	func peek()->Node?
	{
		if (self.top != nil)
		{
			return self.top!.element;
		}
		else
		{
			return 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 string
	//  1) expression can be contains positive number example (1,44,2324,55 etc)
	//  2) Expression contains parentheses which is indicates is left and right child
	//   Example 1 : () null child, other (4) child with node 4
	func construct_tree(_ str: [Character], _ n: Int)->Node?
	{
		//  Define loop controlling variable
		var i: Int = 0;
		//  Define stack variable
		let stack: MyStack = MyStack();
		//  Define some useful Tree node variables
		var auxiliary: Node? = nil;
		var temp: Node? = nil;
		var child: Node? = nil;
		var parent: Node? = nil;
		//  Define some auxiliary variables
		var num: Int = 0;
		var position: Int = 0;
		
		// Construct tree
		while (i < n)
		{
			if (str[i] == "(")
			{
				//  Add null node
				temp = nil;
				stack.push(temp, 0);
				i += 1;
			}
			else if (str[i] == ")")
			{
				if (stack.is_size() < 2)
				{
					// not a valid parent child relation
					return nil;
				}
				position = 0;
				//  Reset the value of parent and child node
				child = nil;
				parent = nil;
				if (stack.is_empty() == false)
				{
					// Get child node
					child = stack.peek();
					stack.pop();
				}
				if (stack.is_empty() == false)
				{
					// Get parent node
					parent = stack.peek();
					position = stack.top!.indicator;
					stack.pop();
				}
				if (parent != nil)
				{
					// connect parent to child node
					if (position == 0)
					{
						//  Add node in left side
						parent!.left = child;
						position = 1;
					}
					else if (position == 1)
					{
						//  Add node in right side
						parent!.right = child;
						position = 2;
					}
					else
					{
						//  Tree exist More than 2 child nodes
						//  example  x(1)(2)(3) x is parent
						print("\n More than 2 child of node ", parent!.data ,"\n", terminator: "");
						return nil;
					}
					stack.push(parent, position);
				}
				i += 1;
			}
			else if (str[i] >= "1" && str[i] <= "9")
			{
				num = 0;
              	var ch : String = " "	;
              
				//  Collect node value
				while (i < n && str[i] != "(" && str[i] != ")")
				{
                  	ch = String(str[i]);
					num = (num * 10) + Int(UnicodeScalar(ch)!.value  - UnicodeScalar("0")!.value);
					i += 1;
				}
				//  Get new tree node
				temp = Node(num);
				if (stack.is_empty() == false)
				{
					auxiliary = stack.peek();
					if (auxiliary == nil)
					{
						//  When stack top node element is empty then add new node to this location
						stack.top!.element = temp;
					}
					else
					{
						//  Add new node in tree
						stack.push(temp, 0);
					}
				}
				else
				{
					//  When stack is empty, then add first node
					stack.push(temp, 0);
				}
			}
			else
			{
				//  When not a valid expression
				print("\n Invalid Expression \n", terminator: "");
				return nil;
			}
		}
		if (stack.is_empty() == false)
		{
			auxiliary = stack.peek();
			stack.pop();
			return auxiliary;
		}
		else
		{
			return nil;
		}
	}
	// handles the request of construct binary tree
	func make_tree(_ str: String, _ n: Int)
	{
		if (n <= 0)
		{
			// Invalid sequence
			self.root = nil;
		}
		else
		{
          	// Display given expression
			print("\n Expression : ", str );
			self.root = self.construct_tree(Array(str), n);
		}
	}
	// 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();
	//  string expression
	let str: String = "16(7(4()(6))(2))(8(9()(1))(3(15)))";
	//  Get the size
	let size: Int = str.count;
	tree.make_tree(str, size);
	// 
	// 		            16
	// 		          /    \
	// 		         /      \
	// 		        /        \
	// 		       7         8
	// 		      /  \     /   \
	// 		     4    2   9     3
	// 		      \        \   /  
	// 		       6        1 15  
	// 		    ----------------  
	// 		    Resultant binary tree
	// 		    
	tree.print_tree();
}
main();

Output

 Expression :  16(7(4()(6))(2))(8(9()(1))(3(15)))

 Preorder :    16   7   4   6   2   8   9   1   3   15
 Inorder :    4   6   7   2   16   9   1   8   15   3
 Postorder :    6   4   2   7   1   9   15   3   8   16




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