Evaluate Expression Tree - 🐓 Spycode

Statement

Evaluate Expression Tree

You’re given a binary expression tree. Write a function to evaluate this tree mathematically and return a single resulting integer.

All leaf nodes in the tree represent operands, which will always be positive integers. All of the other nodes represent operators. There are 4 operators supported, each of which is represented by a negative integer:

-1 : Addition operator, adding the left and right subtrees.

-2 : Subtraction operator, subtracting the right subtree from the left subtree.

-3 : Division operator, dividing the left subtree by the right subtree. If the result is a decimal, it should be rounded towards zero.

-4 : Multiplication operator, multiplying the left and right subtrees.

You can assume the tree will always be a valid expression tree. Each operator also works as a grouping symbol, meaning the bottom of the tree is always evaluated first, regardless of the operator.

BST Representation

tree =           -1
                /   \
              -2     -3
             /  \   /  \
           -4   2  8    3
          / \
         2   3

Solution Explanation

We are given a binary expression tree, where each leaf is a number and each internal node is an operator:

-1 → add, -2 → subtract, -3 → divide, -4 → multiply

To solve it, we evaluate the tree from the bottom to the top. If the node is a number, we return it. If the node is an operator, we first solve the left and right subtrees, and then we apply the correct math operation.

This is why we use recursion — each node depends on the result of its children.

⏱️ Time Complexity O(n).

We must visit every node one time to get the final result from the tree. So, if the tree has n nodes, we do n steps.

➡️ More nodes = more steps, in a straight line. That’s why it’s O(n).

💾 Space Complexity O(h).

h = the height of the tree (how many levels it has from top to bottom).

Because we use recursion, each recursive call is stored in memory until the operation finishes. The computer needs space for each “step” in the path down the tree.

➡️ If the tree is tall, we use more memory. ➡️ If the tree is short, we use less memory.

That’s why it’s O(h).

Soluction

// Define BST class
class BST {
  constructor(value) {
    this.value = value;
    this.left = null;
    this.right = null;
  }
}

function evaluateTree(tree){
 // If it's a positive number, return it
 if(tree.value >=0 ) return tree.value

// Evaluate left and right sides
 const leftValue =  evaluateExpressionTree(tree.left)
 const rightValue =  evaluateExpressionTree(tree.right)

  // Apply the operation
 if (tree.value == -1)
    return leftValue + rightValue
 if (tree.value == -2)
    return leftValue - rightValue
 if (tree.value == -3)
    return  parseInt(leftValue / rightValue)
 if(tree.value == -4)
    return leftValue * rightValue
}

// Build tree

const root = new BST(-1);
root.left = new BST(-2);
root.right = new BST(-3);
root.left.left = new BST(-4);
root.left.right = new BST(2);
root.right.left = new BST(8);
root.right.right = new BST(3);
root.left.left.left = new BST(2);
root.left.left.right = new BST(3);

console.log(evaluateTree(root));

# Evaluate Expression Tree