Evaluate a Binary Expression Tree

Evaluate a given binary expression tree representing algebraic expressions.

A binary expression tree is a binary tree, where the operators are stored in the tree’s internal nodes, and the leaves contain constants.

Assume that each node of the binary expression tree has zero or two children. The supported operators are +(addition), −(subtraction), *(multiplication), ÷(division) and ^(exponentiation).

For example, the value of the following expression tree is 28:

Binary Expression Tree

Practice this problem

We can evaluate an expression tree by applying the operator at the root to values obtained by recursively evaluating left and right subtrees. This can be easily done by traversing the expression tree using postorder traversal. The algorithm can be implemented as follows in C++, Java, and Python:

C++

#include <iostream>

#include <string>

using namespace std;

// Data structure to store a binary tree node

struct Node

{

string val;

Node *left, *right;

Node(string val)

{

this->val = val;

this->left = this->right = nullptr;

}

};

// Utility function to check if a given node is a leaf node

bool isLeaf(Node* node) {

return node->left == nullptr && node->right == nullptr;

}

// Function to apply an operator 'op' to values 'x' and 'y' and return the result

double process(string op, double x, double y)

{

if (op == "+") { return x + y; }

if (op == "-") { return x - y; }

if (op == "*") { return x * y; }

if (op == "/") { return x / y; }

return 0;

}

// Recursive function to evaluate a binary expression tree

double evaluate(Node* root)

{

// base case: invalid input

if (root == nullptr) {

return 0;

}

// the leaves of a binary expression tree are operands

if (isLeaf(root)) {

return stod(root->val);

}

// recursively evaluate the left and right subtree

double x = evaluate(root->left);

double y = evaluate(root->right);

// apply the operator at the root to the values obtained in the previous step

return process(root->val, x, y);

}

int main()

{

Node* root = new Node("+");

root->left = new Node("*");

root->right = new Node("/");

root->left->left = new Node("-");

root->left->right = new Node("5");

root->right->left = new Node("21");

root->right->right = new Node("7");

root->left->left->left = new Node("10");

root->left->left->right = new Node("5");

cout << "The value of the expression tree is " << evaluate(root) << endl;

return 0;

}

Download Run Code

Output:

The value of the expression tree is 28

Java

// Data structure to store a binary tree node

class Node

{

String val;

Node left, right;

Node(String val)

{

this.val = val;

this.left = this.right = null;

}

class Main

{

// Utility function to check if a given node is a leaf node

public static boolean isLeaf(Node node) {

return node.left == null && node.right == null;

}

// Function to apply an operator 'op' to values 'x' and 'y' and return the result

public static double process(String op, double x, double y)

{

if (op.equals("+")) { return x + y; }

if (op.equals("-")) { return x - y; }

if (op.equals("*")) { return x * y; }

if (op.equals("/")) { return x / y; }

return 0;

}

// Recursive function to evaluate a binary expression tree

public static double evaluate(Node root)

{

// base case: invalid input

if (root == null) {

return 0;

}

// the leaves of a binary expression tree are operands

if (isLeaf(root)) {

return Double.valueOf(root.val);

}

// recursively evaluate the left and right subtree

double x = evaluate(root.left);

double y = evaluate(root.right);

// apply the operator at the root to the values obtained in the previous step

return process(root.val, x, y);

}

public static void main(String[] args)

{

Node root = new Node("+");

root.left = new Node("*");

root.right = new Node("/");

root.left.left = new Node("-");

root.left.right = new Node("5");

root.right.left = new Node("21");

root.right.right = new Node("7");

root.left.left.left = new Node("10");

root.left.left.right = new Node("5");

System.out.println("The value of the expression tree is " + evaluate(root));

}

Download Run Code

Output:

The value of the expression tree is 28.0

Python

# Data structure to store a binary tree node

class Node:

def __init__(self, val, left=None, right=None):

self.val = val

self.left = left

self.right = right

# Utility function to check if a given node is a leaf node

def isLeaf(node):

return node.left is None and node.right is None

# Function to apply an operator 'op' to values 'x' and 'y' and return the result

def process(op, x, y):

if op == '+':

return x + y

if op == '-':

return x - y

if op == '*':

return x * y

if op == '/':

return x / y

# Recursive function to evaluate a binary expression tree

def evaluate(root):

# base case: invalid input

if root is None:

return 0

# the leaves of a binary expression tree are operands

if isLeaf(root):

return float(root.val)

# recursively evaluate the left and right subtree

x = evaluate(root.left)

y = evaluate(root.right)

# apply the operator at the root to the values obtained in the previous step

return process(root.val, x, y)

if __name__ == '__main__':

root = Node('+')

root.left = Node('*')

root.right = Node('/')

root.left.left = Node('-')

root.left.right = Node('5')

root.right.left = Node('21')

root.right.right = Node('7')

root.left.left.left = Node('10')

root.left.left.right = Node('5')

print('The value of the expression tree is', evaluate(root))

Download Run Code

Output:

The value of the expression tree is 28.0

The time complexity of the above solution is O(n), where n is the total number of nodes in the expression tree. The auxiliary space required by the program is O(h) for the call stack, where h is the height of the tree.

Evaluate a Binary Expression Tree

C++

Java

Python

Share this: