Design an Expression Tree With Evaluate Function - Solution & Explanation

Problem Overview: You receive a postfix (Reverse Polish Notation) expression and must build an expression tree that can evaluate itself. Each node represents either an operand (number) or an operator (+, -, *, /). The goal is to design the tree structure and implement an evaluate() method that computes the expression result.

Approach 1: Stack-Based Expression Tree Construction (O(n) time, O(n) space)

The postfix expression naturally fits a stack-based algorithm. Iterate through each token in the array. If the token is a number, create a node and push it onto the stack. If the token is an operator, pop two nodes from the stack (right operand first, then left), create a new operator node, and attach the popped nodes as children. Push the new subtree root back onto the stack. After processing all tokens, the stack contains the root of the complete binary tree. Implement evaluate() recursively: leaf nodes return their integer value, while operator nodes evaluate left and right subtrees and apply the stored operator.

This approach works because postfix notation guarantees that operands appear before the operator that uses them. The stack always maintains partially built subtrees until an operator combines them.

Approach 2: Recursive Evaluation on Constructed Tree (O(n) time, O(h) space)

Once the expression tree is built, evaluation becomes a standard tree traversal problem. Each operator node depends on the results of its children, which makes a postorder traversal ideal. Recursively call evaluate() on the left and right children, then apply the operator stored in the current node. Operands immediately return their numeric value.

This recursion uses the call stack proportional to the tree height h. In the worst case (skewed tree) space becomes O(n), but typical expression trees are balanced, keeping recursion depth smaller.

The combination of stack-based construction and recursive evaluation cleanly separates responsibilities: building the structure first, then computing results using tree semantics. This design pattern appears frequently in compiler parsing and interpreter implementations.

Recommended for interviews: The stack-based construction combined with recursive evaluation is the expected solution. It demonstrates understanding of postfix parsing, tree design, and recursion. A brute-force evaluation of the postfix expression alone would miss the key requirement of designing the expression tree class.