Home » Interview coding problems/challenges

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