Evaluate Expression Tree

Tags

Evaluate Expression Tree

Category

Binary Trees

Difficulty

Easy

Problem Statement

Given a binary expression tree where leaf nodes contain integer operands and internal nodes contain one of four operators (+, -, *, /), evaluate the expression represented by the tree and return the result. The operators are typically encoded as negative integers: -1 for addition, -2 for subtraction, -3 for division, -4 for multiplication.

Intuition

An expression tree encodes a mathematical expression structurally: leaves are operands and internal nodes are operators that combine their two children. Evaluating such a tree is a natural fit for post-order traversal — first evaluate the left subtree, then the right subtree, then apply the operator at the current node to the two results.

Approach

  1. If the current node is a leaf (no children), return its value as the operand.
  2. Otherwise, recursively evaluate the left subtree to get leftValue.
  3. Recursively evaluate the right subtree to get rightValue.
  4. Apply the operator stored at the current node to leftValue and rightValue.
  5. Return the result.

Pseudocode

function evaluateExpressionTree(node):
    if node.left is null and node.right is null:
        return node.value

    leftValue = evaluateExpressionTree(node.left)
    rightValue = evaluateExpressionTree(node.right)

    if node.value == -1:      // addition
        return leftValue + rightValue
    else if node.value == -2:  // subtraction
        return leftValue - rightValue
    else if node.value == -3:  // division
        return int(leftValue / rightValue)  // truncate toward zero
    else if node.value == -4:  // multiplication
        return leftValue * rightValue

Time & Space Complexity

  • Time: O(n) where n is the number of nodes. Each node is visited exactly once.
  • Space: O(h) where h is the height of the tree, due to the recursion stack. For a balanced expression tree, this is O(log n).

Key Insights

  • Post-order traversal is the natural evaluation order: compute children before applying the parent operator.
  • Leaf nodes are the base case of the recursion — they hold raw values.
  • Division typically truncates toward zero (integer division), not floor division. This distinction matters for negative operands.
  • The tree structure inherently encodes operator precedence and associativity, so no parentheses or precedence rules are needed.

Edge Cases

  • A tree with a single leaf node: return its value directly.
  • Division by zero: depending on the problem constraints, this may not occur, but it should be considered.
  • Negative operands combined with integer division: ensure truncation toward zero, not floor division (e.g., -7 / 2 = -3, not -4).
  • Very deep expression trees could cause stack overflow with recursion.

Linked mentions