Evaluate a +/- expression tree

Problem A binary tree encodes an arithmetic expression: internal nodes are '+' or '-' operators, leaves are numeric values. Compute the value at the root.

Input / Output

• Input: root of the expression tree.
• Output: evaluated integer.

Constraints

• Tree depth may be large — discuss recursion limits; operators are binary (exactly two children).

Example

• (+ (- 5 2) 3) → 6.

Expected approach

• Post-order recursion: evaluate left and right subtrees, apply the node's operator; leaves return their value. O(n) time, O(h) stack; iterative post-order with an explicit stack avoids deep-recursion overflow. Edge cases to name: single-leaf tree, malformed nodes (operator with missing child), overflow. The design follow-up (see follow-ups) targets polymorphism — evaluate() as a virtual method per node class instead of a type-switch.