Q:

Convert Ternary Expression to Binary Tree

belongs to collection: Interview coding problems/challenges

mahmoud2506
Save to bookmark
|
2022-04-28
|
  286 
0

Given a string that contains ternary expressions. The expressions may be nested. You need to convert the given ternary expression to a binary Tree and return the root.

C++ programming, Interview questions, C++ programming Interview-questions,
login and add your own answer to this question

All Answers

mahmoud2506
2022-04-28
need an explanation for this answer? contact us directly to get an explanation for this answer 

#include <bits/stdc++.h>
using namespace std;

struct Node{
	char data;
	Node *left,*right;
};

//function to create node
Node *newNode(char Data) 
{
	Node *new_node = new Node;
	new_node->data = Data;
	new_node->left = new_node->right = NULL;
	return new_node;
}

//function to traverse preorder
void preorder(Node *root){ 
	if(root==NULL)
		return;
	cout<<root->data<<" ";
	preorder(root->left);
	preorder(root->right);
}

//recursive function to build the tree
Node *convertExpression(string str,int& i) 
{
	Node* root=newNode(str[i]);
	i++;
	if(i<str.length() && str[i]=='?'){
		i++;
		root->left=convertExpression(str,i);
		i++; //skipping ':' character
		root->right=convertExpression(str,i);
	}
	return root;
}


int main(){
	string str;
	
	cout<<"Enter your expression\n";
	cin>>str;
	
	int i=0;
	Node *root=convertExpression(str,i);
	cout<<"Printing pre-order traversal of the tree...\n";
	//pre-order traversal of the tree, 
	//should be same with expressionthe 
	preorder(root);
	cout<<endl;
	
	return 0;
}

need an explanation for this answer? contact us directly to get an explanation for this answer

total answers (1)

Interview coding problems/challenges
This question belongs to these collections

Similar questions

need a help?

find thousands of online teachers now
Write a program to determine Minimum Number of Fli... >>
<< Write a function to find the longest common prefix...