Skip to main content

Convert Ternary Expression to a Binary Tree Using Stack

The problem Convert Ternary Expression to a Binary Tree Using Stack involves converting a given ternary expression into a binary tree representation using a stack data structure. A ternary expression is an expression that involves three operands and two operators: '?' and ':'. The expression has the form a?b:c, which means if the condition a is true, then the value of the expression is b, otherwise it is c.

Problem Statement

Given a ternary expression as a string, we need to construct a binary tree that represents the expression. Each node in the binary tree will have a character value, and the left and right children will represent the 'true' and 'false' conditions, respectively.

Example

Let's consider the following ternary expression:

Expression: "a?b?c:d?e:f:g?h:i"

The corresponding binary tree representation will be as follows:


     a
    / \
   /   \
  b     g
 / \   / \
c   d h   i
   / \  
  e   f

Idea to Solve the Problem

To convert the ternary expression into a binary tree, we can use a stack data structure. The idea is to traverse the expression from left to right and use the stack to keep track of the nodes in the binary tree. We'll perform the following steps:

  1. Initialize an empty stack and a result node to store the root of the binary tree.
  2. Traverse the expression from left to right.
  3. For each character in the expression: a. If it is a question mark '?', push the top element of the stack as the left child of the new node and push the new node onto the stack. b. If it is a colon ':', pop elements from the stack until a node with no right child is found. The top element of the stack will be the parent node of the new node, and the new node will be its right child. c. If it is any other character, create a new node with the character value and push it onto the stack.
  4. Continue the traversal until the entire expression is processed.
  5. The root of the binary tree will be the top element of the stack.

Algorithm

  1. Initialize an empty stack and a result node.
  2. Traverse the expression from left to right using a loop with index i.
  3. For each character exp[i] in the expression: a. If exp[i] is a question mark '?': i. Pop the top element from the stack and set it as the left child of a new node temp. ii. Push temp onto the stack. b. If exp[i] is a colon ':': i. Pop elements from the stack until a node with no right child is found. Set this node as the parent node of a new node temp. ii. Set temp as the right child of the parent node. c. If exp[i] is any other character: i. Create a new node temp with the character value exp[i]. ii. Push temp onto the stack.
  4. The top element of the stack will be the root of the binary tree.

Pseudocode

Function construct_tree(exp, n):
    Create an empty stack
    Create variables auxiliary, temp, result and status

    For i = 0 to n-1:
        If exp[i] is a question mark '?':
            If stack is not empty and next element is valid:
                Pop the top element from the stack and set it as left child of temp
                Push temp onto the stack
                Increment i by 2
            Else:
                Set status to false
        Else if exp[i] is a colon ':':
            If stack is not empty and next element is valid:
                Pop elements from the stack until a node with no right child is found. Set the top element of stack as parent of temp
                Set temp as the right child of parent
                Set status to false
                Set auxiliary to null
                While stack is not empty and status is false:
                    Set auxiliary to top element of stack
                    If auxiliary has no right child:
                        Set status to true
                    Else:
                        Pop an element from stack
            Else:
                Set status to false
        Else:
            Create a new node temp with value exp[i]
            If result is null:
                Set result to temp
            Push temp onto the stack

    If status is true:
        Return result
    Else:
        Print "Invalid Expression"
        Return null

Code Solution

/*
    C Program 
    Convert Ternary Expression to a Binary Tree
    Using Stack
*/
#include <stdio.h>

#include <stdlib.h>

//Binary Tree node
struct Node
{
	char data;
	struct Node *left, *right;
};
struct MyStack
{
	struct Node *element;
	struct MyStack *next;
};
//Create a MyStack element and return this reference
struct MyStack *push(struct Node *tree_node, struct MyStack **top)
{
	struct MyStack *node = (struct MyStack *) malloc(sizeof(struct MyStack));
	if (node != NULL)
	{
		//set pointer values
		node->element = tree_node;
		node->next = *top;*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(char 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("  %c", node->data);
		print_inorder(node->right);
	}
}
//Display pre order elements
void print_preorder(struct Node *node)
{
	if (node != NULL)
	{
		//Print node value
		printf("  %c", 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("  %c", node->data);
	}
}
// Check whether next node is valid in expression
int is_valid(char exp[], int i, int n)
{
	if (i + 1 < n && exp[i + 1] != '?' && exp[i + 1] != ':')
	{
		return 1;
	}
	else
	{
		return 0;
	}
}
// Construct a binary tree using of ternary expression
struct Node *construct_tree(char exp[], int n)
{
	// Define loop controlling variable
	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 *result = NULL;
	// used to detect valid expression
	int status = 1;
	//Display given expression
	printf("\n Expression : %s\n", exp);
	//Construct tree
	while (i < n && status == 1)
	{
		if (exp[i] == '?')
		{
			if (top != NULL && is_valid(exp, i, n))
			{
				//Add next element in left side
				auxiliary = top->element;
				temp = get_node(exp[i + 1]);
				auxiliary->left = temp;
				push(temp, & top);
				i += 2;
			}
			else
			{
				status = 0;
			}
		}
		else if (exp[i] == ':')
		{
			if (top != NULL && is_valid(exp, i, n))
			{
				// next element in right child
				pop( & top);
				status = 0;
				auxiliary = NULL;
				// Find correct valid node to add new node in right side
				while (top != NULL && status == 0)
				{
					// Get the top element of stack
					auxiliary = top->element;
					if (auxiliary->right == NULL)
					{
						//When parent node exists
						status = 1;
					}
					else
					{
						pop( & top);
					}
				}
				if (status == 1)
				{
					// Create new node
					temp = get_node(exp[i + 1]);
					// Add node in right side
					auxiliary->right = temp;
					push(temp, & top);
					i += 2;
				}
			}
			else
			{
				status = 0;
			}
		}
		else
		{
			//Add new node
			temp = get_node(exp[i]);
			if (result == NULL)
			{
				result = temp;
			}
			push(temp, & top);
			i++;
		}
	}
	if (status == 1)
	{
		return result;
	}
	else
	{
		printf("\n Invalid Expression \n");
		return NULL;
	}
}
//handles the request of construct binary tree
struct Node *make_tree(char exp[], int n)
{
	if (n <= 0)
	{
		//Invalid sequence
		return NULL;
	}
	else
	{
		return construct_tree(exp, 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 exp[] = "a?b?c:d?e:f:g?h:i";
	// Get the size
	int size = sizeof(exp) / sizeof(exp[0]) - 1;
	struct Node *root = make_tree(exp, size);
	/*
	Resultant binary tree
	----------------------
	     a
	    / \ 
	   /   \
	  b     g
	 / \   / \
	c   d h   i
	   / \  
	  e   f
	----------------------
	Preorder :   a  b  c  d  e  f  g  h  i
	Inorder :   c  b  e  d  f  a  h  g  i
	Postorder :   c  e  f  d  b  h  i  g  a
	*/
	print_tree(root);
	return 0;
}

Output

 Expression : a?b?c:d?e:f:g?h:i

 Preorder :   a  b  c  d  e  f  g  h  i
 Inorder :   c  b  e  d  f  a  h  g  i
 Postorder :   c  e  f  d  b  h  i  g  a
/*
    Java Program 
    Convert Ternary Expression to a Binary Tree
    Using Stack
*/
// Binary Tree node
class Node
{
    public char data;
    public Node left;
    public Node right;
    public Node(char data)
    {
        // Set node value
        this.data = data;
        this.left = null;
        this.right = null;
    }
}
//Stack Node
class StackNode
{
    public Node element;
    public StackNode next;
    public StackNode(Node element)
    {
        this.element = element;
        this.next = null;
    }
}
//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)
    {
        //Make a new stack node
        StackNode new_node = new StackNode(element);
        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 BinaryTree()
    {
        //Set root of tree
        this.root = null;
    }
    //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);
        }
    }
    // Check whether next node is valid in expression
    public boolean is_valid(String exp, int i, int n)
    {
        if (i + 1 < n && exp.charAt(i + 1) != '?' && exp.charAt(i + 1) != ':')
        {
            return true;
        }
        else
        {
            return false;
        }
    }
    // Construct a binary tree using of ternary expression
    public Node construct_tree(String exp, int n)
    {
        // Define loop controlling variable
        int i = 0;
        // Define stack variable
        MyStack stack = new MyStack();
        // Define some useful tree node variables
        Node auxiliary = null;
        Node temp = null;
        Node result = null;
        // used to detect valid expression
        boolean status = true;
        //Display given expression
        System.out.print("\n Expression : " + exp + "\n");
        //Construct tree
        while (i < n && status == true)
        {
            if (exp.charAt(i) == '?')
            {
                if (stack.is_empty() == false && is_valid(exp, i, n))
                {
                    //Add next element in left side
                    auxiliary = stack.peek();
                    temp = new Node(exp.charAt(i + 1));
                    auxiliary.left = temp;
                    stack.push(temp);
                    i += 2;
                }
                else
                {
                    status = false;
                }
            }
            else if (exp.charAt(i) == ':')
            {
                if (stack.is_empty() == false && is_valid(exp, i, n))
                {
                    // next element in right child
                    stack.pop();
                    status = false;
                    auxiliary = null;
                    // Find correct valid node to add new node in right side
                    while (stack.is_empty() == false && status == false)
                    {
                        // Get the top element of stack
                        auxiliary = stack.peek();
                        if (auxiliary.right == null)
                        {
                            //When parent node exists
                            status = true;
                        }
                        else
                        {
                            stack.pop();
                        }
                    }
                    if (status == true)
                    {
                        // Create new node
                        temp = new Node(exp.charAt(i + 1));
                        // Add node in right side
                        auxiliary.right = temp;
                        stack.push(temp);
                        i += 2;
                    }
                }
                else
                {
                    status = false;
                }
            }
            else
            {
                //Add new node
                temp = new Node(exp.charAt(i));
                if (result == null)
                {
                    result = temp;
                }
                stack.push(temp);
                i++;
            }
        }
        if (status == true)
        {
            return result;
        }
        else
        {
            System.out.print("\n Invalid Expression \n");
            return null;
        }
    }
    //handles the request of construct binary tree
    public void make_tree(String exp, int n)
    {
        if (n <= 0)
        {
            //Invalid sequence
            this.root = null;
        }
        else
        {
            this.root = construct_tree(exp, 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 exp = "a?b?c:d?e:f:g?h:i";
      	int size = exp.length();
        tree.make_tree(exp, size);
        /*
        Resultant binary tree
        ----------------------
             a
            / \ 
           /   \
          b     g
         / \   / \
        c   d h   i
           / \  
          e   f
        ----------------------
        Preorder :   a  b  c  d  e  f  g  h  i
        Inorder :   c  b  e  d  f  a  h  g  i
        Postorder :   c  e  f  d  b  h  i  g  a
        */
        tree.print_tree();
    }
}

Output

 Expression : a?b?c:d?e:f:g?h:i

 Preorder :   a  b  c  d  e  f  g  h  i
 Inorder :   c  b  e  d  f  a  h  g  i
 Postorder :   c  e  f  d  b  h  i  g  a
// Include header file
#include <iostream>
using namespace std;

//  C++ Program 
//  Convert Ternary Expression to a Binary Tree
//  Using Stack

//  Binary Tree node
class Node
{
	public: 
    char data;
	Node *left;
	Node *right;
	Node(char data)
	{
		//  Set node value
		this->data = data;
		this->left = NULL;
		this->right = NULL;
	}
};
// Stack Node
class StackNode
{
	public: Node *element;
	StackNode *next;
	StackNode(Node *element)
	{
		this->element = element;
		this->next = NULL;
	}
};
// 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)
	{
		// Make a new stack node
		StackNode *new_node = new StackNode(element);
		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;
	BinaryTree()
	{
		// Set root of tree
		this->root = NULL;
	}
	// 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;
		}
	}
	//  Check whether next node is valid in expression
	bool is_valid(string exp, int i, int n)
	{
		if (i + 1 < n && exp[i + 1] != '?' && exp[i + 1] != ':')
		{
			return true;
		}
		else
		{
			return false;
		}
	}
	//  Construct a binary tree using of ternary expression
	Node *construct_tree(string exp, int n)
	{
		//  Define loop controlling variable
		int i = 0;
		//  Define stack variable
		MyStack stack = MyStack();
		//  Define some useful tree node variables
		Node *auxiliary = NULL;
		Node *temp = NULL;
		Node *result = NULL;
		//  used to detect valid expression
		bool status = true;
		// Display given expression
		cout << "\n Expression : " << exp << "\n";
		// Construct tree
		while (i < n && status == true)
		{
			if (exp[i] == '?')
			{
				if (stack.is_empty() == false && this->is_valid(exp, i, n))
				{
					// Add next element in left side
					auxiliary = stack.peek();
					temp = new Node(exp[i + 1]);
					auxiliary->left = temp;
					stack.push(temp);
					i += 2;
				}
				else
				{
					status = false;
				}
			}
			else if (exp[i] == ':')
			{
				if (stack.is_empty() == false && this->is_valid(exp, i, n))
				{
					//  next element in right child
					stack.pop();
					status = false;
					auxiliary = NULL;
					//  Find correct valid node to add new node in right side
					while (stack.is_empty() == false && status == false)
					{
						//  Get the top element of stack
						auxiliary = stack.peek();
						if (auxiliary->right == NULL)
						{
							// When parent node exists
							status = true;
						}
						else
						{
							stack.pop();
						}
					}
					if (status == true)
					{
						//  Create new node
						temp = new Node(exp[i + 1]);
						//  Add node in right side
						auxiliary->right = temp;
						stack.push(temp);
						i += 2;
					}
				}
				else
				{
					status = false;
				}
			}
			else
			{
				// Add new node
				temp = new Node(exp[i]);
				if (result == NULL)
				{
					result = temp;
				}
				stack.push(temp);
				i++;
			}
		}
		if (status == true)
		{
			return result;
		}
		else
		{
			cout << "\n Invalid Expression \n";
			return NULL;
		}
	}
	// handles the request of construct binary tree
	void make_tree(string exp, int n)
	{
		if (n <= 0)
		{
			// Invalid sequence
			this->root = NULL;
		}
		else
		{
			this->root = this->construct_tree(exp, 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 exp = "a?b?c:d?e:f:g?h:i";
	int size = exp.length();
	tree.make_tree(exp, size);
	// 
	// 		Resultant binary tree
	// 		----------------------
	// 		     a
	// 		    / \ 
	// 		   /   \
	// 		  b     g
	// 		 / \   / \
	// 		c   d h   i
	// 		   / \  
	// 		  e   f
	// 		----------------------
	// 		Preorder :   a  b  c  d  e  f  g  h  i
	// 		Inorder :   c  b  e  d  f  a  h  g  i
	// 		Postorder :   c  e  f  d  b  h  i  g  a
	// 		
	tree.print_tree();
	return 0;
}

Output

 Expression : a?b?c:d?e:f:g?h:i

 Preorder :   a  b  c  d  e  f  g  h  i
 Inorder :   c  b  e  d  f  a  h  g  i
 Postorder :   c  e  f  d  b  h  i  g  a
// Include namespace system
using System;

//  C# Program 
//  Convert Ternary Expression to a Binary Tree
//  Using Stack

//  Binary Tree node
public class Node
{
	public char data;
	public Node left;
	public Node right;
	public Node(char 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 StackNode(Node element)
	{
		this.element = element;
		this.next = null;
	}
}
// 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)
	{
		// Make a new stack node
		StackNode new_node = new StackNode(element);
		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 BinaryTree()
	{
		// Set root of tree
		this.root = null;
	}
	// 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);
		}
	}
	//  Check whether next node is valid in expression
	public Boolean is_valid(String exp, int i, int n)
	{
		if (i + 1 < n && exp[i + 1] != '?' && exp[i + 1] != ':')
		{
			return true;
		}
		else
		{
			return false;
		}
	}
	//  Construct a binary tree using of ternary expression
	public Node construct_tree(String exp, int n)
	{
		//  Define loop controlling variable
		int i = 0;
		//  Define stack variable
		MyStack stack = new MyStack();
		//  Define some useful tree node variables
		Node auxiliary = null;
		Node temp = null;
		Node result = null;
		//  used to detect valid expression
		Boolean status = true;
		// Display given expression
		Console.Write("\n Expression : " + exp + "\n");
		// Construct tree
		while (i < n && status == true)
		{
			if (exp[i] == '?')
			{
				if (stack.is_empty() == false && is_valid(exp, i, n))
				{
					// Add next element in left side
					auxiliary = stack.peek();
					temp = new Node(exp[i + 1]);
					auxiliary.left = temp;
					stack.push(temp);
					i += 2;
				}
				else
				{
					status = false;
				}
			}
			else if (exp[i] == ':')
			{
				if (stack.is_empty() == false && is_valid(exp, i, n))
				{
					//  next element in right child
					stack.pop();
					status = false;
					auxiliary = null;
					//  Find correct valid node to add new node in right side
					while (stack.is_empty() == false && status == false)
					{
						//  Get the top element of stack
						auxiliary = stack.peek();
						if (auxiliary.right == null)
						{
							// When parent node exists
							status = true;
						}
						else
						{
							stack.pop();
						}
					}
					if (status == true)
					{
						//  Create new node
						temp = new Node(exp[i + 1]);
						//  Add node in right side
						auxiliary.right = temp;
						stack.push(temp);
						i += 2;
					}
				}
				else
				{
					status = false;
				}
			}
			else
			{
				// Add new node
				temp = new Node(exp[i]);
				if (result == null)
				{
					result = temp;
				}
				stack.push(temp);
				i++;
			}
		}
		if (status == true)
		{
			return result;
		}
		else
		{
			Console.Write("\n Invalid Expression \n");
			return null;
		}
	}
	// handles the request of construct binary tree
	public void make_tree(String exp, int n)
	{
		if (n <= 0)
		{
			// Invalid sequence
			this.root = null;
		}
		else
		{
			this.root = construct_tree(exp, 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 exp = "a?b?c:d?e:f:g?h:i";
		int size = exp.Length;
		tree.make_tree(exp, size);
		// 
		// 		Resultant binary tree
		// 		----------------------
		// 		     a
		// 		    / \ 
		// 		   /   \
		// 		  b     g
		// 		 / \   / \
		// 		c   d h   i
		// 		   / \  
		// 		  e   f
		// 		----------------------
		// 		Preorder :   a  b  c  d  e  f  g  h  i
		// 		Inorder :   c  b  e  d  f  a  h  g  i
		// 		Postorder :   c  e  f  d  b  h  i  g  a
		// 		
		tree.print_tree();
	}
}

Output

 Expression : a?b?c:d?e:f:g?h:i

 Preorder :   a  b  c  d  e  f  g  h  i
 Inorder :   c  b  e  d  f  a  h  g  i
 Postorder :   c  e  f  d  b  h  i  g  a
<?php
/*
    Php Program 
    Convert Ternary Expression to a Binary Tree
    Using Stack
*/
//  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;

	function __construct($element)
	{
		$this->element = $element;
		$this->next = null;
	}
}
// 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)
	{
		// Make a new stack node
		$new_node = new StackNode($element);
		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;

	function __construct()
	{
		// Set root of tree
		$this->root = null;
	}
	// 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;
		}
	}
	//  Check whether next node is valid in expression
	public	function is_valid($exp, $i, $n)
	{
		if ($i + 1 < $n && $exp[$i + 1] != '?' && $exp[$i + 1] != ':')
		{
			return true;
		}
		else
		{
			return false;
		}
	}
	//  Construct a binary tree using of ternary expression
	public	function construct_tree($exp, $n)
	{
		//  Define loop controlling variable
		$i = 0;
		//  Define stack variable
		$stack = new MyStack();
		//  Define some useful tree node variables
		$auxiliary = null;
		$temp = null;
		$result = null;
		//  used to detect valid expression
		$status = true;
		// Display given expression
		echo "\n Expression : ". $exp ."\n";
		// Construct tree
		while ($i < $n && $status == true)
		{
			if ($exp[$i] == '?')
			{
				if ($stack->is_empty() == false && $this->is_valid($exp, $i, $n))
				{
					// Add next element in left side
					$auxiliary = $stack->peek();
					$temp = new Node($exp[$i + 1]);
					$auxiliary->left = $temp;
					$stack->push($temp);
					$i += 2;
				}
				else
				{
					$status = false;
				}
			}
			else if ($exp[$i] == ':')
			{
				if ($stack->is_empty() == false && $this->is_valid($exp, $i, $n))
				{
					//  next element in right child
					$stack->pop();
					$status = false;
					$auxiliary = null;
					//  Find correct valid node to add new node in right side
					while ($stack->is_empty() == false && $status == false)
					{
						//  Get the top element of stack
						$auxiliary = $stack->peek();
						if ($auxiliary->right == null)
						{
							// When parent node exists
							$status = true;
						}
						else
						{
							$stack->pop();
						}
					}
					if ($status == true)
					{
						//  Create new node
						$temp = new Node($exp[$i + 1]);
						//  Add node in right side
						$auxiliary->right = $temp;
						$stack->push($temp);
						$i += 2;
					}
				}
				else
				{
					$status = false;
				}
			}
			else
			{
				// Add new node
				$temp = new Node($exp[$i]);
				if ($result == null)
				{
					$result = $temp;
				}
				$stack->push($temp);
				$i++;
			}
		}
		if ($status == true)
		{
			return $result;
		}
		else
		{
			echo "\n Invalid Expression \n";
			return null;
		}
	}
	// handles the request of construct binary tree
	public	function make_tree($exp, $n)
	{
		if ($n <= 0)
		{
			// Invalid sequence
			$this->root = null;
		}
		else
		{
			$this->root = $this->construct_tree($exp, $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();
	$exp = "a?b?c:d?e:f:g?h:i";
	$size = strlen($exp);
	$tree->make_tree($exp, $size);
	/*
			Resultant binary tree
			----------------------
			     a
			    / \ 
			   /   \
			  b     g
			 / \   / \
			c   d h   i
			   / \  
			  e   f
			----------------------
			Preorder :   a  b  c  d  e  f  g  h  i
			Inorder :   c  b  e  d  f  a  h  g  i
			Postorder :   c  e  f  d  b  h  i  g  a
	*/
	$tree->print_tree();
}
main();

Output

 Expression : a?b?c:d?e:f:g?h:i

 Preorder :   a  b  c  d  e  f  g  h  i
 Inorder :   c  b  e  d  f  a  h  g  i
 Postorder :   c  e  f  d  b  h  i  g  a
/*
    Node Js Program 
    Convert Ternary Expression to a Binary Tree
    Using Stack
*/
//  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)
	{
		this.element = element;
		this.next = null;
	}
}
// Define custom stack and its operation
class MyStack
{
	constructor()
	{
		this.top = null;
		this.length = 0;
	}
	// Add a new element in stack
	push(element)
	{
		// Make a new stack node
		var new_node = new StackNode(element);
		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;
	}
	// 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);
		}
	}
	//  Check whether next node is valid in expression
	is_valid(exp, i, n)
	{
		if (i + 1 < n && exp[i + 1] != '?' && exp[i + 1] != ':')
		{
			return true;
		}
		else
		{
			return false;
		}
	}
	//  Construct a binary tree using of ternary expression
	construct_tree(exp, 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 result = null;
		//  used to detect valid expression
		var status = true;
		// Display given expression
		process.stdout.write("\n Expression : " + exp + "\n");
		// Construct tree
		while (i < n && status == true)
		{
			if (exp[i] == '?')
			{
				if (stack.is_empty() == false && this.is_valid(exp, i, n))
				{
					// Add next element in left side
					auxiliary = stack.peek();
					temp = new Node(exp[i + 1]);
					auxiliary.left = temp;
					stack.push(temp);
					i += 2;
				}
				else
				{
					status = false;
				}
			}
			else if (exp[i] == ':')
			{
				if (stack.is_empty() == false && this.is_valid(exp, i, n))
				{
					//  next element in right child
					stack.pop();
					status = false;
					auxiliary = null;
					//  Find correct valid node to add new node in right side
					while (stack.is_empty() == false && status == false)
					{
						//  Get the top element of stack
						auxiliary = stack.peek();
						if (auxiliary.right == null)
						{
							// When parent node exists
							status = true;
						}
						else
						{
							stack.pop();
						}
					}
					if (status == true)
					{
						//  Create new node
						temp = new Node(exp[i + 1]);
						//  Add node in right side
						auxiliary.right = temp;
						stack.push(temp);
						i += 2;
					}
				}
				else
				{
					status = false;
				}
			}
			else
			{
				// Add new node
				temp = new Node(exp[i]);
				if (result == null)
				{
					result = temp;
				}
				stack.push(temp);
				i++;
			}
		}
		if (status == true)
		{
			return result;
		}
		else
		{
			process.stdout.write("\n Invalid Expression \n");
			return null;
		}
	}
	// handles the request of construct binary tree
	make_tree(exp, n)
	{
		if (n <= 0)
		{
			// Invalid sequence
			this.root = null;
		}
		else
		{
			this.root = this.construct_tree(exp, 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();
	var exp = "a?b?c:d?e:f:g?h:i";
	var size = exp.length;
	tree.make_tree(exp, size);
	/*
			Resultant binary tree
			----------------------
			     a
			    / \ 
			   /   \
			  b     g
			 / \   / \
			c   d h   i
			   / \  
			  e   f
			----------------------
			Preorder :   a  b  c  d  e  f  g  h  i
			Inorder :   c  b  e  d  f  a  h  g  i
			Postorder :   c  e  f  d  b  h  i  g  a
	*/
	tree.print_tree();
}
main();

Output

 Expression : a?b?c:d?e:f:g?h:i

 Preorder :   a  b  c  d  e  f  g  h  i
 Inorder :   c  b  e  d  f  a  h  g  i
 Postorder :   c  e  f  d  b  h  i  g  a
#     Python 3 Program 
#     Convert Ternary Expression to a Binary Tree
#     Using Stack

#  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) :
		self.element = element
		self.next = None
	

# 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) :
		# Make a new stack node
		new_node = StackNode(element)
		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
	
	# 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 = "")
		
	
	#  Check whether next node is valid in expression
	def is_valid(self, exp, i, n) :
		if (i + 1 < n and exp[i + 1] != '?'
			and exp[i + 1] != ':') :
			return True
		else :
			return False
		
	
	#  Construct a binary tree using of ternary expression
	def construct_tree(self, exp, n) :
		#  Define loop controlling variable
		i = 0
		#  Define stack variable
		stack = MyStack()
		#  Define some useful tree node variables
		auxiliary = None
		temp = None
		result = None
		#  used to detect valid expression
		status = True
		# Display given expression
		print("\n Expression : ", exp ,"\n", end = "")
		# Construct tree
		while (i < n and status == True) :
			if (exp[i] == '?') :
				if (stack.is_empty() == False and self.is_valid(exp, i, n)) :
					# Add next element in left side
					auxiliary = stack.peek()
					temp = Node(exp[i + 1])
					auxiliary.left = temp
					stack.push(temp)
					i += 2
				else :
					status = False
				
			
			elif(exp[i] == ':') :
				if (stack.is_empty() == False and self.is_valid(exp, i, n)) :
					#  next element in right child
					stack.pop()
					status = False
					auxiliary = None
					#  Find correct valid node to add new node in right side
					while (stack.is_empty() == False and status == False) :
						#  Get the top element of stack
						auxiliary = stack.peek()
						if (auxiliary.right == None) :
							# When parent node exists
							status = True
						else :
							stack.pop()
						
					
					if (status == True) :
						#  Create new node
						temp = Node(exp[i + 1])
						#  Add node in right side
						auxiliary.right = temp
						stack.push(temp)
						i += 2
					
				else :
					status = False
				
			else :
				# Add new node
				temp = Node(exp[i])
				if (result == None) :
					result = temp
				
				stack.push(temp)
				i += 1
			
		
		if (status == True) :
			return result
		else :
			print("\n Invalid Expression \n", end = "")
			return None
		
	
	# handles the request of construct binary tree
	def make_tree(self, exp, n) :
		if (n <= 0) :
			# Invalid sequence
			self.root = None
		else :
			self.root = self.construct_tree(exp, 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()
	exp = "a?b?c:d?e:f:g?h:i"
	size = len(exp)
	tree.make_tree(exp, size)
	# 
	# 		Resultant binary tree
	# 		----------------------
	# 		     a
	# 		    / \ 
	# 		   /   \
	# 		  b     g
	# 		 / \   / \
	# 		c   d h   i
	# 		   / \  
	# 		  e   f
	# 		----------------------
	# 		Preorder :   a  b  c  d  e  f  g  h  i
	# 		Inorder :   c  b  e  d  f  a  h  g  i
	# 		Postorder :   c  e  f  d  b  h  i  g  a
	# 		
	
	tree.print_tree()

if __name__ == "__main__": main()

Output

 Expression :  a?b?c:d?e:f:g?h:i

 Preorder :    a   b   c   d   e   f   g   h   i
 Inorder :    c   b   e   d   f   a   h   g   i
 Postorder :    c   e   f   d   b   h   i   g   a
#     Ruby Program 
#     Convert Ternary Expression to a Binary Tree
#     Using Stack

#  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
	attr_accessor :element, :next
 
	
	def initialize(element) 
		self.element = element
		self.next = nil
	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) 
		# Make a new stack node
		new_node = StackNode.new(element)
		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
	attr_accessor :root
 
	
	def initialize() 
		# Set root of tree
		self.root = nil
	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

	#  Check whether next node is valid in expression
	def is_valid(exp, i, n) 
		if (i + 1 < n && exp[i + 1] != '?' && exp[i + 1] != ':') 
			return true
		else 
			return false
		end

	end

	#  Construct a binary tree using of ternary expression
	def construct_tree(exp, n) 
		#  Define loop controlling variable
		i = 0
		#  Define stack variable
		stack = MyStack.new()
		#  Define some useful tree node variables
		auxiliary = nil
		temp = nil
		result = nil
		#  used to detect valid expression
		status = true
		# Display given expression
		print("\n Expression : ", exp ,"\n")
		# Construct tree
		while (i < n && status == true) 
			if (exp[i] == '?') 
				if (stack.is_empty() == false && self.is_valid(exp, i, n)) 
					# Add next element in left side
					auxiliary = stack.peek()
					temp = Node.new(exp[i + 1])
					auxiliary.left = temp
					stack.push(temp)
					i += 2
				else 
					status = false
				end

			elsif(exp[i] == ':') 
				if (stack.is_empty() == false && self.is_valid(exp, i, n)) 
					#  next element in right child
					stack.pop()
					status = false
					auxiliary = nil
					#  Find correct valid node to add new node in right side
					while (stack.is_empty() == false && status == false) 
						#  Get the top element of stack
						auxiliary = stack.peek()
						if (auxiliary.right == nil) 
							# When parent node exists
							status = true
						else 
							stack.pop()
						end

					end

					if (status == true) 
						#  Create new node
						temp = Node.new(exp[i + 1])
						#  Add node in right side
						auxiliary.right = temp
						stack.push(temp)
						i += 2
					end

				else 
					status = false
				end

			else 
				# Add new node
				temp = Node.new(exp[i])
				if (result == nil) 
					result = temp
				end

				stack.push(temp)
				i += 1
			end

		end

		if (status == true) 
			return result
		else 
			print("\n Invalid Expression \n")
			return nil
		end

	end

	# handles the request of construct binary tree
	def make_tree(exp, n) 
		if (n <= 0) 
			# Invalid sequence
			self.root = nil
		else 
			self.root = self.construct_tree(exp, 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()
	exp = "a?b?c:d?e:f:g?h:i"
	size = exp.length()
	tree.make_tree(exp, size)
	# 
	# 		Resultant binary tree
	# 		----------------------
	# 		     a
	# 		    / \ 
	# 		   /   \
	# 		  b     g
	# 		 / \   / \
	# 		c   d h   i
	# 		   / \  
	# 		  e   f
	# 		----------------------
	# 		Preorder :   a  b  c  d  e  f  g  h  i
	# 		Inorder :   c  b  e  d  f  a  h  g  i
	# 		Postorder :   c  e  f  d  b  h  i  g  a
	# 		
	
	tree.print_tree()
end

main()

Output

 Expression : a?b?c:d?e:f:g?h:i

 Preorder :   a  b  c  d  e  f  g  h  i
 Inorder :   c  b  e  d  f  a  h  g  i
 Postorder :   c  e  f  d  b  h  i  g  a

/*
    Scala Program 
    Convert Ternary Expression to a Binary Tree
    Using Stack
*/
//  Binary Tree node
class Node(var data: Character , var left: Node , var right: Node)
{
	def this(data: Char)
	{
		this(data, null, null);
	}
}
// Stack Node
class StackNode(var element: Node , var next: StackNode)
{
	def this(element: Node)
	{
		this(element, null);
	}
}
// 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): Unit = {
		// Make a new stack node
		var new_node: StackNode = new StackNode(element);
		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)
{
	def this()
	{
		this(null);
	}
	// 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);
		}
	}
	//  Check whether next node is valid in expression
	def is_valid(exp: String, i: Int, n: Int): Boolean = {
		if (i + 1 < n && exp(i + 1) != '?' && exp(i + 1) != ':')
		{
			return true;
		}
		else
		{
			return false;
		}
	}
	//  Construct a binary tree using of ternary expression
	def construct_tree(exp: 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 result: Node = null;
		//  used to detect valid expression
		var status: Boolean = true;
		// Display given expression
		print("\n Expression : " + exp + "\n");
		// Construct tree
		while (i < n && status == true)
		{
			if (exp(i) == '?')
			{
				if (stack.is_empty() == false && is_valid(exp, i, n))
				{
					// Add next element in left side
					auxiliary = stack.peek();
					temp = new Node(exp(i + 1));
					auxiliary.left = temp;
					stack.push(temp);
					i += 2;
				}
				else
				{
					status = false;
				}
			}
			else if (exp(i) == ':')
			{
				if (stack.is_empty() == false && is_valid(exp, i, n))
				{
					//  next element in right child
					stack.pop();
					status = false;
					auxiliary = null;
					//  Find correct valid node to add new node in right side
					while (stack.is_empty() == false && status == false)
					{
						//  Get the top element of stack
						auxiliary = stack.peek();
						if (auxiliary.right == null)
						{
							// When parent node exists
							status = true;
						}
						else
						{
							stack.pop();
						}
					}
					if (status == true)
					{
						//  Create new node
						temp = new Node(exp(i + 1));
						//  Add node in right side
						auxiliary.right = temp;
						stack.push(temp);
						i += 2;
					}
				}
				else
				{
					status = false;
				}
			}
			else
			{
				// Add new node
				temp = new Node(exp(i));
				if (result == null)
				{
					result = temp;
				}
				stack.push(temp);
				i += 1;
			}
		}
		if (status == true)
		{
			return result;
		}
		else
		{
			print("\n Invalid Expression \n");
			return null;
		}
	}
	// handles the request of construct binary tree
	def make_tree(exp: String, n: Int): Unit = {
		if (n <= 0)
		{
			// Invalid sequence
			this.root = null;
		}
		else
		{
			this.root = construct_tree(exp, 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();
		var exp: String = "a?b?c:d?e:f:g?h:i";
		var size: Int = exp.length();
		tree.make_tree(exp, size);
		/*
				Resultant binary tree
				----------------------
				     a
				    / \ 
				   /   \
				  b     g
				 / \   / \
				c   d h   i
				   / \  
				  e   f
				----------------------
				Preorder :   a  b  c  d  e  f  g  h  i
				Inorder :   c  b  e  d  f  a  h  g  i
				Postorder :   c  e  f  d  b  h  i  g  a
				*/
		tree.print_tree();
	}
}

Output

 Expression : a?b?c:d?e:f:g?h:i

 Preorder :   a  b  c  d  e  f  g  h  i
 Inorder :   c  b  e  d  f  a  h  g  i
 Postorder :   c  e  f  d  b  h  i  g  a
/*
    Swift 4 Program 
    Convert Ternary Expression to a Binary Tree
    Using Stack
*/
//  Binary Tree node
class Node
{
	var data: Character;
	var left: Node? ;
	var right: Node? ;
	init(_ data: Character)
	{
		//  Set node value
		self.data = data;
		self.left = nil;
		self.right = nil;
	}
}
// Stack Node
class StackNode
{
	var element: Node? ;
	var next: StackNode? ;
	init(_ element: Node? )
	{
		self.element = element;
		self.next = nil;
	}
}
// 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? )
	{
		// Make a new stack node
		let new_node: StackNode? = StackNode(element);
		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? ;
	init()
	{
		// Set root of tree
		self.root = nil;
	}
	// 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: "");
		}
	}
	//  Check whether next node is valid in expression
	func is_valid(_ exp: [Character], _ i: Int, _ n: Int)->Bool
	{
		if (i + 1 < n && exp[i + 1] != "?" && exp[i + 1] != ":")
		{
			return true;
		}
		else
		{
			return false;
		}
	}
	//  Construct a binary tree using of ternary expression
	func construct_tree(_ exp: [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 result: Node? = nil;
		//  used to detect valid expression
		var status: Bool = true;
		
		// Construct tree
		while (i < n && status == true)
		{
			if (exp[i] == "?")
			{
				if (stack.is_empty() == false && self.is_valid(exp, i, n))
				{
					// Add next element in left side
					auxiliary = stack.peek();
					temp = Node(exp[i + 1]);
					auxiliary!.left = temp;
					stack.push(temp);
					i += 2;
				}
				else
				{
					status = false;
				}
			}
			else if (exp[i] == ":")
			{
				if (stack.is_empty() == false && self.is_valid(exp, i, n))
				{
					//  next element in right child
					stack.pop();
					status = false;
					auxiliary = nil;
					//  Find correct valid node to add new node in right side
					while (stack.is_empty() == false && status == false)
					{
						//  Get the top element of stack
						auxiliary = stack.peek();
						if (auxiliary!.right == nil)
						{
							// When parent node exists
							status = true;
						}
						else
						{
							stack.pop();
						}
					}
					if (status == true)
					{
						//  Create new node
						temp = Node(exp[i + 1]);
						//  Add node in right side
						auxiliary!.right = temp;
						stack.push(temp);
						i += 2;
					}
				}
				else
				{
					status = false;
				}
			}
			else
			{
				// Add new node
				temp = Node(exp[i]);
				if (result == nil)
				{
					result = temp;
				}
				stack.push(temp);
				i += 1;
			}
		}
		if (status == true)
		{
			return result;
		}
		else
		{
			print("\n Invalid Expression \n", terminator: "");
			return nil;
		}
	}
	// handles the request of construct binary tree
	func make_tree(_ exp: String, _ n: Int)
	{
		if (n <= 0)
		{
			// Invalid sequence
			self.root = nil;
		}
		else
		{
          	// Display given expression
			print("\n Expression : ", exp );
			self.root = self.construct_tree(Array(exp), 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();
	let exp: String = "a?b?c:d?e:f:g?h:i";
	let size: Int = exp.count;
	tree.make_tree(exp, size);
	/*
		Resultant binary tree
		----------------------
		     a
		    / \ 
		   /   \
		  b     g
		 / \   / \
		c   d h   i
		   / \  
		  e   f
		----------------------
		Preorder :   a  b  c  d  e  f  g  h  i
		Inorder :   c  b  e  d  f  a  h  g  i
		Postorder :   c  e  f  d  b  h  i  g  a
		*/
	tree.print_tree();
}
main();

Output

 Expression :  a?b?c:d?e:f:g?h:i

 Preorder :    a   b   c   d   e   f   g   h   i
 Inorder :    c   b   e   d   f   a   h   g   i
 Postorder :    c   e   f   d   b   h   i   g   a

Time Complexity

The time complexity of the algorithm is O(n), where n is the number of characters in the ternary expression. The algorithm processes each character in the expression once, and the stack operations take constant time. Therefore, the overall time complexity is linear.

Last updated on by Kalkicode




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