LeetCode 1628 - Design an Expression Tree With Evaluate Function

The problem requires constructing a binary expression tree from a postfix arithmetic expression and implementing a metho

leetcodemediumarraymathstacktreedesignbinary-tree

LeetCode Problem 1628

Difficulty: 🟡 Medium
Topics: Array, Math, Stack, Tree, Design, Binary Tree

Solution

Problem Understanding

The problem requires constructing a binary expression tree from a postfix arithmetic expression and implementing a method to evaluate the tree. The input is an array of strings postfix representing numbers and operators (+, -, *, /) in postfix notation, meaning operands appear before their operators. The output is the root node of a binary tree in which leaf nodes are numbers and internal nodes are operators. The evaluate function, when called on the root, must compute the value of the expression represented by the tree.

The constraints clarify that the input is always valid, numbers are ≤ 10^5, the length of postfix is odd (ensuring a proper postfix expression), and no intermediate or final result exceeds 10^9. This guarantees that a correct algorithm does not need to handle division by zero or malformed expressions. Edge cases primarily involve single-element expressions (just a number) and expressions with multiple nested operators.

Approaches

A brute-force approach might involve recursively parsing the postfix expression by repeatedly scanning for the first operator and splitting the array into left and right operands. While correct, this approach repeatedly copies subarrays and scans the array, leading to O(n^2) time complexity and O(n) space complexity for recursion.

The optimal approach uses a stack. The key insight is that in postfix notation, when we encounter an operator, the two most recent operands (or subtrees) on the stack become its children. By iterating once through the array and using a stack to maintain partially built trees, we can build the entire tree efficiently in O(n) time and O(n) space. Each element is pushed and popped at most once, and we only maintain pointers to subtrees rather than copying arrays.

Approach Time Complexity Space Complexity Notes
Brute Force O(n^2) O(n) Repeatedly scans and splits arrays to construct the tree
Stack-Based Optimal O(n) O(n) Iterates once through postfix array using stack to build tree

Algorithm Walkthrough

  1. Initialize a stack to hold partially constructed nodes of type Node.
  2. Iterate through the postfix array:
  • If the token is a number, create a LeafNode representing this number and push it onto the stack.
  • If the token is an operator, pop the last two nodes from the stack; these become the right and left children of a new OperatorNode representing the operator. Push this new node back onto the stack.
  1. After the iteration, the stack contains exactly one node, which is the root of the expression tree.
  2. Evaluate the tree recursively by calling the evaluate method on the root. Leaf nodes return their numeric value; operator nodes recursively evaluate their left and right subtrees and apply the operator.

Why it works: Postfix notation guarantees that when an operator appears, the two previous elements are exactly the operands for that operator. Using a stack preserves this order and allows constant-time construction of each node.

Python Solution

from typing import List
import abc
from abc import ABC, abstractmethod

class Node(ABC):
    @abstractmethod
    def evaluate(self) -> int:
        pass

class LeafNode(Node):
    def __init__(self, value: int):
        self.value = value
    
    def evaluate(self) -> int:
        return self.value

class OperatorNode(Node):
    def __init__(self, operator: str, left: Node, right: Node):
        self.operator = operator
        self.left = left
        self.right = right
    
    def evaluate(self) -> int:
        lval = self.left.evaluate()
        rval = self.right.evaluate()
        if self.operator == '+':
            return lval + rval
        elif self.operator == '-':
            return lval - rval
        elif self.operator == '*':
            return lval * rval
        elif self.operator == '/':
            return int(lval / rval)  # truncate towards zero
        else:
            raise ValueError(f"Unknown operator: {self.operator}")

class TreeBuilder(object):
    def buildTree(self, postfix: List[str]) -> 'Node':
        stack: List[Node] = []
        for token in postfix:
            if token in '+-*/':
                right = stack.pop()
                left = stack.pop()
                stack.append(OperatorNode(token, left, right))
            else:
                stack.append(LeafNode(int(token)))
        return stack[0]

Explanation: LeafNode stores numeric values, OperatorNode stores an operator and its left/right subtrees. The TreeBuilder iterates through the postfix array, pushing leaf nodes or combining the last two nodes for operators. Evaluation is recursive, propagating computations from leaves to root.

Go Solution

package main

import (
	"strconv"
)

type Node interface {
	Evaluate() int
}

type LeafNode struct {
	value int
}

func (n *LeafNode) Evaluate() int {
	return n.value
}

type OperatorNode struct {
	operator string
	left     Node
	right    Node
}

func (n *OperatorNode) Evaluate() int {
	lval := n.left.Evaluate()
	rval := n.right.Evaluate()
	switch n.operator {
	case "+":
		return lval + rval
	case "-":
		return lval - rval
	case "*":
		return lval * rval
	case "/":
		return lval / rval
	default:
		panic("Unknown operator")
	}
}

type TreeBuilder struct{}

func (tb *TreeBuilder) BuildTree(postfix []string) Node {
	stack := []Node{}
	for _, token := range postfix {
		switch token {
		case "+", "-", "*", "/":
			right := stack[len(stack)-1]
			left := stack[len(stack)-2]
			stack = stack[:len(stack)-2]
			stack = append(stack, &OperatorNode{token, left, right})
		default:
			val, _ := strconv.Atoi(token)
			stack = append(stack, &LeafNode{val})
		}
	}
	return stack[0]
}

Notes: Go uses slices for the stack and requires explicit type casting. Integer division truncates toward zero, which aligns with Python's int(a / b) behavior.

Worked Examples

Example 1: ["3","4","+","2","*","7","/"]

Step Stack Content Action
3 [3] Push LeafNode(3)
4 [3,4] Push LeafNode(4)
+ [+Node(3,4)] Pop 3,4 → OperatorNode('+')
2 [+Node, 2] Push LeafNode(2)
* [*Node(+Node,2)] Pop +Node,2 → OperatorNode('*')
7 [*Node,7] Push LeafNode(7)
/ [/Node(*Node,7)] Pop *Node,7 → OperatorNode('/')

Evaluation: ((3+4)*2)/7 = 14/7 = 2

Example 2: ["4","5","2","7","+","-","*"]

Step Stack Content Action
4 [4] Push LeafNode(4)
5 [4,5] Push LeafNode(5)
2 [4,5,2] Push LeafNode(2)
7 [4,5,2,7] Push LeafNode(7)
+ [4,5,+Node(2,7)] Pop 2,7 → OperatorNode('+')
- [4,-Node(5,+Node)] Pop 5,+Node → OperatorNode('-')
* [*Node(4,-Node)] Pop 4,-Node → OperatorNode('*')

Evaluation: 4 * (5-(2+7)) = 4*(-4) = -16

Complexity Analysis

Measure Complexity Explanation
Time O(n) Each token is processed once, pushing/popping at most once
Space O(n) Stack stores at most n/2 intermediate nodes during construction

The linear complexity is justified because postfix notation allows constant-time construction per token, avoiding repeated scans.

Test Cases

# Provided examples
assert TreeBuilder().buildTree(["3","4","+","2","*","7","/"]).evaluate() == 2
assert TreeBuilder().buildTree(["4","5","2","7","+","-","*"]).evaluate() == -16

# Single number
assert TreeBuilder().buildTree(["42"]).evaluate() == 42

# Simple addition
assert TreeBuilder().buildTree(["1","2","+"]).evaluate() == 3

# Nested multiplication and division
assert TreeBuilder().buildTree(["6","3","2","*","/"]).evaluate() == 1  # 6 / (3*2) = 1

# All operators
assert TreeBuilder().buildTree(["10","5","-","2","*","3","/"]).evaluate() == 3  # ((10-5)*2)/3 = 10/3 = 3
Test Why
["3","4","+","2","*","7","/"] Standard example, multiple operators
`["4","5","