Leetcode 1628 Design an Expression Tree With Evaluate Function

Problem statement

https://leetcode.com/problems/design-an-expression-tree-with-evaluate-function/

Solution

The most difficult part for me in this problem was that it was not clear what exaclty we need to implement, we need to do two things:

Create expression tree given postfix notation.
Create evaluate class for this tree, which will return executed value.

So, in fact you can say there is two problems hidden in one

To create expression tree we use stack: traverse element by element and when we see symbol among +-*/, we extract two elements from stack and attach them to node. Notice that first extracted element we need to attach as the right children of node and the second extracted element ad the left children.
To evaluate expression tree we need to run it recursively: if we have number, just return its value. If we have +-*/, run it recursively.

Complexity

It is both O(n) to build expression tree and to evaluate it for time. For space we need O(n) for our stack and for tree as well.

Code

class Node:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None
    
    def evaluate(self):
        funcs = {}
        funcs["+"] = lambda x, y: x + y
        funcs["-"] = lambda x, y: x - y
        funcs["*"] = lambda x, y: x * y
        funcs["/"] = lambda x, y: x // y
        if self.val in "+-*/":
            return funcs[self.val](self.left.evaluate(), self.right.evaluate())
        return int(self.val)

class TreeBuilder:
    def buildTree(self, postfix):
        stack = []
        for c in postfix:
            node = Node(c)
            if c in "+-*/":
                node.right = stack.pop()
                node.left = stack.pop()
            stack.append(node)
           
        return stack[0]