Problem Description

You need to build a binary expression tree from a postfix expression and evaluate it.

Input: An array of strings representing a postfix expression, where:

• Numbers (operands) are represented as strings like "4", "5", "7", "2"
• Operators are represented as "+", "-", "*", "/"

Output: A binary expression tree (implemented using the Node interface) that represents the given postfix expression.

Example: For the infix expression 4*(5-(7+2)), the postfix representation is ["4","5","7","2","+","-","*"]. You need to construct a tree that evaluates to the correct result.

Binary Expression Tree Structure:

• Leaf nodes (0 children) contain operands (numbers)
• Internal nodes (2 children) contain operators
• Each operator node has exactly two children (left and right subtrees)

Key Requirements:

1. Implement the Node interface with an evaluate() method that computes the value of the tree
2. Create a TreeBuilder class with a buildTree() method that constructs the tree from the postfix expression
3. The tree should correctly evaluate mathematical expressions using standard operator precedence

Postfix Notation: In postfix notation, operators come after their operands. For example:

• Infix: 5 + 7 becomes Postfix: ["5", "7", "+"]
• Infix: 4 * (5 - (7 + 2)) becomes Postfix: ["4", "5", "7", "2", "+", "-", "*"]

Constraints:

• All operations are valid (no division by zero)
• No subtree will evaluate to a value exceeding 10^9 in absolute value
• The expression will only contain the four basic arithmetic operators: +, -, *, /

Follow-up Challenge: Design your solution to be modular enough to support additional operators without modifying the existing evaluate() implementation.

Intuition

The key insight for solving this problem comes from understanding how postfix expressions are evaluated. When we manually evaluate a postfix expression, we scan from left to right and:

• When we see a number, we remember it for later use
• When we see an operator, we immediately apply it to the most recent two numbers we've seen

This naturally suggests using a stack data structure. Think about it: we need to store numbers as we encounter them, and when we hit an operator, we need the two most recently stored numbers - this is exactly what a stack gives us with its Last-In-First-Out (LIFO) property.

But here's the clever part: instead of just storing numbers on the stack and computing values, we can store tree nodes instead. This way, we're building the tree structure as we process the expression.

The construction process mirrors the evaluation process:

1. When we encounter a number (operand), we create a leaf node and push it onto the stack
2. When we encounter an operator, we:
   • Pop two nodes from the stack (these become the children)
   • Create a new node with the operator as its value
   • Make the popped nodes its children (careful with the order - the first popped becomes the right child, the second becomes the left child)
   • Push this new subtree back onto the stack

Why does this work? Because in postfix notation, an operator always appears immediately after all of its operands have been fully specified. By the time we see an operator, we've already built the complete subtrees for its operands, and they're sitting on top of the stack waiting to be combined.

At the end of processing all tokens, the stack contains exactly one element - the root of our complete expression tree. This root represents the entire expression, with all operations properly structured according to the original postfix notation.

The beauty of this approach is that it builds the tree in a single pass through the postfix expression, with each token being processed exactly once, giving us an efficient O(n) solution.

Learn more about Stack, Tree, Math and Binary Tree patterns.

Solution Approach

The implementation uses a stack-based approach to construct the binary expression tree from the postfix notation. Let's walk through the key components:

Node Implementation

First, we implement the MyNode class that extends the abstract Node interface:

class MyNode(Node):
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

Each node stores:

• val: The value (either a number as a string or an operator)
• left: Reference to the left child
• right: Reference to the right child

The evaluate() method recursively computes the value:

• If the node contains a digit (leaf node), it returns the integer value
• If the node contains an operator (internal node), it:
  1. Recursively evaluates the left and right subtrees
  2. Applies the operator to the results

Tree Construction Algorithm

The buildTree method implements the core algorithm:

def buildTree(self, postfix: List[str]) -> 'Node':
    stk = []
    for s in postfix:
        node = MyNode(s)
        if not s.isdigit():
            node.right = stk.pop()
            node.left = stk.pop()
        stk.append(node)
    return stk[-1]

Step-by-step process:

1. Initialize an empty stack stk

2. Iterate through each token s in the postfix expression:

   • Create a new node with value s

3. Check if the token is an operator (not a digit):

   • If it's an operator:
     • Pop the top node from stack → becomes the right child
     • Pop the next node from stack → becomes the left child
     • Note: The order matters! The first popped node is the right child because of how postfix notation works

4. Push the current node onto the stack:

   • If it was a number, we push a leaf node
   • If it was an operator, we push a subtree with the operator as root

5. After processing all tokens, the stack contains exactly one element - the root of the complete expression tree

Example Walkthrough

For postfix expression ["4", "5", "7", "2", "+", "-", "*"]:

1. Process "4": Push leaf node(4) → Stack: [4]
2. Process "5": Push leaf node(5) → Stack: [4, 5]
3. Process "7": Push leaf node(7) → Stack: [4, 5, 7]
4. Process "2": Push leaf node(2) → Stack: [4, 5, 7, 2]
5. Process "+": Pop 2 and 7, create node(+) with children → Stack: [4, 5, (7+2)]
6. Process "-": Pop (7+2) and 5, create node(-) with children → Stack: [4, (5-(7+2))]
7. Process "": Pop (5-(7+2)) and 4, create node() with children → Stack: [(4*(5-(7+2)))]

The final stack contains the root of the tree representing 4*(5-(7+2)).

Time and Space Complexity

• Time Complexity: O(n) where n is the number of tokens. Each token is processed exactly once.
• Space Complexity: O(n) for the stack and the resulting tree structure.

The solution elegantly leverages the properties of postfix notation where operators always appear after their operands, making it perfect for stack-based processing.

Example Walkthrough

Let's walk through a simple example with the postfix expression ["3", "4", "+", "2", "*"], which represents the infix expression (3 + 4) * 2.

Step-by-step construction:

Initial state: Stack = []

Step 1: Process "3"

• Create a leaf node with value "3"
• It's a digit, so no children needed
• Push to stack
• Stack = [Node(3)]

Step 2: Process "4"

• Create a leaf node with value "4"
• It's a digit, so no children needed
• Push to stack
• Stack = [Node(3), Node(4)]

Step 3: Process "+"

• Create a node with value "+"
• It's an operator, so we need children:
  • Pop Node(4) → becomes right child
  • Pop Node(3) → becomes left child
• Create the subtree:

    +
   / \
  3   4

• Push this subtree to stack
• Stack = [Node(+) with children 3 and 4]

Step 4: Process "2"

• Create a leaf node with value "2"
• It's a digit, so no children needed
• Push to stack
• Stack = [Node(+) with children 3 and 4, Node(2)]

Step 5: Process "*"

• Create a node with value "*"
• It's an operator, so we need children:
  • Pop Node(2) → becomes right child
  • Pop Node(+) with its subtree → becomes left child
• Create the final tree:

      *
     / \
    +   2
   / \
  3   4

• Push this tree to stack
• Stack = [Node(*) as root of complete tree]

Final Result: The stack contains one element - the root of our expression tree.

Evaluation: When we call evaluate() on the root:

1. Root is "*", so evaluate left and right children
2. Left child is "+", so evaluate its children: 3 + 4 = 7
3. Right child is "2", return 2
4. Apply multiplication: 7 * 2 = 14

The tree correctly evaluates to 14, which matches (3 + 4) * 2 = 14.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n) where n is the length of the postfix expression array.

• The buildTree method iterates through each element in the postfix array exactly once, performing O(1) operations for each element (creating a node, popping from stack, appending to stack). This results in O(n) time for building the tree.
• The evaluate method performs a post-order traversal of the expression tree. Each node is visited exactly once, and at each node, we perform O(1) operations (arithmetic operations or returning a value). Since the tree has n nodes (one for each element in the postfix expression), this also takes O(n) time.
• Overall time complexity: O(n) + O(n) = O(n)

Space Complexity: O(n) where n is the length of the postfix expression array.

• The buildTree method uses a stack that can contain at most (n+1)/2 nodes in the worst case (when all operands appear before all operators). This occurs with expressions like "3 4 5 + *" where operands stack up before being consumed by operators.
• The expression tree itself contains exactly n nodes, requiring O(n) space.
• The evaluate method uses the call stack for recursion. In the worst case (a completely unbalanced tree), the recursion depth can be O(n). In a balanced expression tree, the recursion depth would be O(log n).
• Overall space complexity: O(n) for the tree structure plus O(n) for either the build stack or the recursion stack in the worst case, resulting in O(n) total space complexity.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect Order When Popping Children for Operators

One of the most frequent mistakes is reversing the order when assigning left and right children during tree construction. Since a stack follows LIFO (Last In, First Out) order, the operands are popped in reverse order of how they appear in the original expression.

Incorrect Implementation:

if not token.isdigit():
    node.left = stack.pop()   # Wrong! This gets the second operand
    node.right = stack.pop()  # Wrong! This gets the first operand

Why This Fails: For the expression 5 - 3 with postfix ["5", "3", "-"]:

• Stack after processing "5" and "3": [5, 3]
• When processing "-", if we incorrectly assign:
  • node.left = stack.pop() → left = 3
  • node.right = stack.pop() → right = 5
• This creates the tree representing 3 - 5 = -2 instead of 5 - 3 = 2

Correct Implementation:

if not token.isdigit():
    node.right = stack.pop()  # Pop second operand first (becomes right child)
    node.left = stack.pop()   # Pop first operand second (becomes left child)

2. Integer Division Handling

Another common mistake involves division operations, particularly with negative numbers.

Potential Issue:

elif self.value == '/':
    return left_result / right_result  # Wrong! Returns float

Problems:

• Python's / operator returns a float, not an integer
• The behavior of integer division with negative numbers can be unexpected
• Python's // operator floors toward negative infinity, not toward zero

Better Implementation for C++/Java-like Behavior:

elif self.value == '/':
    # For behavior consistent with C++/Java (truncation toward zero)
    return int(left_result / right_result)
    # Or use // for Python's floor division (toward negative infinity)
    # return left_result // right_result

3. Not Handling Negative Numbers in Input

The current implementation assumes all numeric tokens are positive single digits using isdigit(). This fails for negative numbers.

Problem Scenario:

postfix = ["-5", "3", "+"]  # Represents -5 + 3
# The token "-5" would be incorrectly treated as an operator

Robust Solution:

def is_operator(self, token: str) -> bool:
    return token in {'+', '-', '*', '/'}

def buildTree(self, postfix: List[str]) -> Node:
    stack = []
    for token in postfix:
        node = ExpressionNode(token)
        if self.is_operator(token):
            node.right = stack.pop()
            node.left = stack.pop()
        stack.append(node)
    return stack[-1]

4. Empty Stack or Invalid Postfix Expression

The code doesn't validate that the postfix expression is well-formed.

Potential Failures:

# Not enough operands
postfix = ["5", "+"]  # Stack underflow when popping

# Too many operands
postfix = ["5", "3", "2"]  # Multiple nodes left in stack

# Empty input
postfix = []  # IndexError when accessing stack[-1]

Defensive Implementation:

def buildTree(self, postfix: List[str]) -> Node:
    if not postfix:
        raise ValueError("Empty postfix expression")
  
    stack = []
    for token in postfix:
        node = ExpressionNode(token)
        if not token.isdigit():
            if len(stack) < 2:
                raise ValueError(f"Invalid postfix: insufficient operands for {token}")
            node.right = stack.pop()
            node.left = stack.pop()
        stack.append(node)
  
    if len(stack) != 1:
        raise ValueError(f"Invalid postfix: {len(stack)} expressions remaining")
  
    return stack[0]

5. Memory Management in Follow-up Extension

When extending to support more operators, avoid modifying the evaluate method directly. Instead, use a strategy pattern or operator mapping:

Extensible Design:

class ExpressionNode(Node):
    # Define operator functions as a class variable
    OPERATORS = {
        '+': lambda a, b: a + b,
        '-': lambda a, b: a - b,
        '*': lambda a, b: a * b,
        '/': lambda a, b: a // b,
        # Easy to add more operators
        '^': lambda a, b: a ** b,
        '%': lambda a, b: a % b,
    }
  
    def evaluate(self) -> int:
        if self.value.isdigit():
            return int(self.value)
      
        left_result = self.left.evaluate()
        right_result = self.right.evaluate()
      
        if self.value in self.OPERATORS:
            return self.OPERATORS[self.value](left_result, right_result)
        else:
            raise ValueError(f"Unknown operator: {self.value}")

These pitfalls highlight the importance of careful attention to stack operations, proper handling of edge cases, and designing for extensibility from the start.