# Expression Tree

In this article, we are going to see what an expression tree is and how to evaluate an expression tree? This problem has been featured in the interview round of Amazon. Submitted by Radib Kar, on February 07, 2019

## Problem statement

Given an expression tree evaluate the expression tree.

## Example

```        *
/ \
+   -
/ \ / \
7  4 6  3

The evaluation will be:
(7+4)*(6-3)
=11* 3=33
```

## Solution

Expression tree:

Any infix expression can be converted to an expression tree whose leaf nodes are all operands & intermediate nodes are operators.

Algorithm to evaluate an expression tree

Expression tree can be evaluated using the following algorithm

```    IF root is operator
Result =  evaluation of left child treeoperator
(root->data) evaluation of right child tree
ELSE
Result = root->data //operand
```

This can be constructed using a recursive function evalTree (root of expression tree)

Pre-requisite functions:

isOperator(string s) = Boolean function to check whether root data is operator or not

```ex:
isOperator("*") returns true where as isOperator("12") returns false
-----------------------------------------------------------------

value(string s)= returns value of the operand represented in string from
ex:
value("12") returns 12
-----------------------------------------------------------------

Evaluate (int a, int b, string s):  returns the result of evaluation
where a, b are operands and s is the operator
IF(s=="*")
return a*b;
ELSE IF(s=="/")
return a/b;
ELSE IF(s=="+")
return a+b;
ELSE
return a-b;
```
```FUNCTION evalTree(root)
1.  Base case
IF (root==NULL)
Return 0;
2.  IF (isOperator(root->data))
Evaluate left subtree (say a),
evaluate right subtree(say b) and return a root->data b
Set a=evalTree (root->left);
Set b=evalTree (root->left);
Return evaluate(a, b, tree->data);
ELSE
Return value (root->data); //return operand value
END FUNCTION
```

## C++ Implementation

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

// TreeNode node type
class TreeNode{
public:
string data;       //data
TreeNode *left;    //pointer to left child
TreeNode *right;   //pointer to right child
};

// creating new node
TreeNode* newnode(string s)
{
TreeNode* node = (TreeNode*)malloc(sizeof(TreeNode));
node->data = s;
node->left = NULL;
node->right = NULL;

return(node);
}

//evalutes a root->data b
int evaluate(int a, int b, string s){
if(s=="*")
return a*b;
else if(s=="/")
return a/b;
else if(s=="+")
return a+b;
else
return a-b;
}

//returns operand value
int value(string s){
int sum=0,p=1;
for(int i=s.length()-1;i>=0;i--){
sum+=p*(s[i]-'0');
p*=10;
}
return sum;
}

//function to check whether operator
bool isOperator(string s){
if(s=="*" || s=="/" || s=="-" || s=="+" )
return true;
return false;
}

//recursive functuon to evaluate
int evalTree(TreeNode* root)
{
if(!root)
return 0;

if(isOperator(root->data)){
int a=evalTree(root->left);
int b=evalTree(root->right);
return evaluate(a,b,root->data);
}
else{
return value(root->data);
}
}

int main(){
cout<<"tree is built as per example\n";

TreeNode *root=newnode("*");

root->left= newnode("+");
root->right= newnode("-");
root->right->right=newnode("3");
root->right->left=newnode("6");
root->left->left=newnode("7");
root->left->right=newnode("4");

cout<<"The evaluation of the expression tree results to: "<<evalTree(root)<<endl;

return 0;
}
```

Output

```tree is built as per example
The evaluation of the expression tree results to: 33
```