Accept prefix expressions, and construct a Binary tree and perform recursive and non-recursive traversal.

CODE:

#include <iostream>

#include <stack>

#include <cctype>

using namespace std;

struct Node {

char data;

Node* left;

Node* right;

Node(char value) : data(value), left(nullptr), right(nullptr) {}

};

bool isOperand(char c) {

return isalnum(c);

}

Node* constructTree(string prefix) {

stack<Node*> st;

for (int i = prefix.length() - 1; i >= 0; i--) {

char c = prefix[i];

if (isOperand(c))

{

st.push(new Node(c));

}

else

{

Node* operand1 = st.top(); st.pop();

Node* operand2 = st.top(); st.pop();

Node* newNode = new Node(c);

newNode->left = operand1;

newNode->right = operand2;

st.push(newNode);

}

}

return st.top();

}

void inorderTraversal(Node* root) {

if (root) {

inorderTraversal(root->left);

cout << root->data << " ";

inorderTraversal(root->right);

}

}

int main()

{

string prefixExpression;

cout << "Enter the prefix expression: ";

cin >> prefixExpression;

Node* root = constructTree(prefixExpression);

cout << "Inorder Traversal: ";

inorderTraversal(root);

return 0;

}