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:
- Initialize an empty stack and a result node to store the root of the binary tree.
- Traverse the expression from left to right.
- 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.
- Continue the traversal until the entire expression is processed.
- The root of the binary tree will be the top element of the stack.
Algorithm
- Initialize an empty stack and a result node.
- Traverse the expression from left to right using a loop with index
i
. - For each character
exp[i]
in the expression: a. Ifexp[i]
is a question mark '?': i. Pop the top element from the stack and set it as the left child of a new nodetemp
. ii. Pushtemp
onto the stack. b. Ifexp[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 nodetemp
. ii. Settemp
as the right child of the parent node. c. Ifexp[i]
is any other character: i. Create a new nodetemp
with the character valueexp[i]
. ii. Pushtemp
onto the stack. - 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.
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