Question

Write a C++ function that takes in an arithmetic expression in prefix notation and converts it into a binary tree, such that each operation is stored in a node whose left subtree stores the left operand, and whose right subtree stores the right operand.

Answer 1

code in c++ for prefix to binary tree (code to copy)

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

// class for tree node
class TreeNode{
public:
char value;
TreeNode *left;
TreeNode *right;
TreeNode(char data){
value=data;
left=NULL;
right=NULL;
}
};
// this function returns if a character is an operator
bool isOperator(char ch){
if (ch == '+' || ch == '-' ||
ch == '*' || ch == '/' ||
ch == '^')
return true;
return false;
}
//inorder traversal of the tree
void inorder(TreeNode* root){
if(root==NULL){
return;
}
inorder(root->left);
cout<<root->value<<" ";
inorder(root->right);
}
int constructTreeFromPrefix(TreeNode** root, string prefix, int cur_pos=0){
if(cur_pos==prefix.size()){
//this is the end of the expression
return cur_pos;
}
//recursively build the expression tree
while(1){
int new_pos;
if(*root==NULL){
//create a new node with the current character in data
TreeNode* newNode = new TreeNode(prefix[cur_pos]);
*root=newNode;
}else{
//check if this character is an operand
if(!isOperator(prefix[cur_pos])){
return cur_pos;
}

//build the left tree
new_pos = constructTreeFromPrefix(&(*root)->left, prefix, cur_pos+1);

//build the right tree
new_pos =constructTreeFromPrefix(&(*root)->right, prefix, new_pos+1);

return cur_pos;
}
}
}

// Driver program to test above
int main()
{
TreeNode* root = NULL;
string prefix = "*+ab-cd";
constructTreeFromPrefix(&root, prefix);
cout<<"Tree is created. Inorder traversal of tree: ";
inorder(root);
return 0;
}
code screenshot

Console Output Screenshot

/*If this helps you, please let me know by giving a positive thumbs up. In case you have any queries, do let me know. I will revert back to you. Thank you!!*/