Leetcode #1628: Design an Expression Tree With Evaluate Function
In this guide, we solve Leetcode #1628 Design an Expression Tree With Evaluate Function in Python and focus on the core idea that makes the solution efficient.
You will see the intuition, the step-by-step method, and a clean Python implementation you can use in interviews.
Problem Statement
Given the postfix tokens of an arithmetic expression, build and return the binary expression tree that represents this expression. Postfix notation is a notation for writing arithmetic expressions in which the operands (numbers) appear before their operators.
Quick Facts
- Difficulty: Medium
- Premium: Yes
- Tags: Stack, Tree, Design, Array, Math, Binary Tree
Intuition
The problem has a natural nested or last-in-first-out structure.
A stack lets us resolve matches in the correct order as we scan.
Approach
Push items as they appear and pop when you can finalize a decision.
The stack captures the unresolved part of the input.
Steps:
- Push elements as you scan.
- Pop when a rule or match is satisfied.
- Use the stack to compute results.
Example
Input: s = ["3","4","+","2","*","7","/"]
Output: 2
Explanation: this expression evaluates to the above binary tree with expression ((3+4)*2)/7) = 14/7 = 2.
Python Solution
import abc
from abc import ABC, abstractmethod
"""
This is the interface for the expression tree Node.
You should not remove it, and you can define some classes to implement it.
"""
class Node(ABC):
# define your fields here
def evaluate(self) -> int:
pass
class MyNode(Node):
def __init__(self, val):
self.val = val
self.left = None
self.right = None
def evaluate(self) -> int:
x = self.val
if x.isdigit():
return int(x)
left, right = self.left.evaluate(), self.right.evaluate()
if x == '+':
return left + right
if x == '-':
return left - right
if x == '*':
return left * right
if x == '/':
return left // right
"""
This is the TreeBuilder class.
You can treat it as the driver code that takes the postinfix input
and returns the expression tree represnting it as a Node.
"""
class TreeBuilder(object):
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]
"""
Your TreeBuilder object will be instantiated and called as such:
obj = TreeBuilder();
expTree = obj.buildTree(postfix);
ans = expTree.evaluate();
"""
Complexity
The time complexity is O(n). The space complexity is O(n).
Edge Cases and Pitfalls
Watch for boundary values, empty inputs, and duplicate values where applicable. If the problem involves ordering or constraints, confirm the invariant is preserved at every step.
Summary
This Python solution focuses on the essential structure of the problem and keeps the implementation interview-friendly while meeting the constraints.