1628. Design an Expression Tree With Evaluate Function

Problem Description

The given LeetCode problem requires us to construct a binary expression tree (BET) from an arithmetic expression provided in postfix notation. In postfix notation, also known as Reverse Polish Notation (RPN), operators come after their operands. For example, 3 4 + would correspond to 3 + 4 in standard infix notation.

The challenge includes implementing a Node interface using the provided Node class, which we are not allowed to remove. We can, however, add our custom fields and methods. The crucial method in the Node class is evaluate, which should compute the value of the subtree rooted at the given node.

The expression tree we need to build is a binary tree, where each leaf node represents an operand (a number), and internal nodes represent operators (+, -, *, /).

We are assured in the problem statement that the expressions are all valid (meaning, for instance, that there won't be any division by zero), and the result of evaluating any subtree will not exceed 10^9 in absolute value.

The problem also encourages us to think about modularity: how to design the expression tree such that it could support additional operators without the need for changing the existing evaluate implementation.

Intuition

To solve this problem, we can iterate over the postfix tokens and use a stack to help build the binary expression tree. Here is the step-by-step approach:

Create an empty stack, which we will use to hold nodes that are yet to be attached to the tree.
Iterate over the postfix tokens.
For each token:
- If the token is a number, simply create a node for this operand and push it onto the stack.
- If the token is an operator, we must create an operator node. Since we're dealing with binary operators, we need to pop two nodes from the stack to be the children of this operator node. The node popped last should be the right child, and the node popped first should be the left child (because of the nature of postfix notation).
- Push the newly created operator node back onto the stack.
After processing all tokens, the stack should only contain one node, which represents the root of our binary expression tree.

The key idea behind this approach is that in postfix expressions, operators always immediately follow their operands, so when we encounter an operator, its operands are the two most recent operands (or subexpressions) that we have processed.

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

Solution Approach

The implementation of the solution for constructing the binary expression tree from postfix tokens involves a clear understanding of stack data structures and object-oriented programming.

Here's how the solution is approached:

Utilizing the Stack Data Structure: A stack is the ideal data structure for this kind of problem because it naturally fits the "Last In, First Out" (LIFO) property of postfix expressions. When processing an operator, its operands are the two most recently encountered values or subexpressions. Therefore, we use a stack to keep track of nodes that have not yet been connected.
Creating the Node Classes: We define a class MyNode that implements the abstract base class Node. The MyNode class holds an integer value for operand nodes or a character value for operator nodes, along with pointers to left and right child nodes.
Implementing the evaluate Method: In the MyNode class, the evaluate method is implemented recursively. It checks if the current node is an operand (a number) or an operator ('+', '-', '*', '/'). If it's an operand, it returns its value as an integer. If it's an operator, it evaluates the left and right subtrees and applies the operator to these evaluated results.
Constructing the Tree: The buildTree method of the TreeBuilder class takes an array of postfix tokens as input. It iterates through each token and performs actions based on whether the token is an operand or an operator:
- If it's an operand, create a new MyNode with the operand as its value and push it on the stack.
- If it's an operator, create a new MyNode with the operator as its value, pop two nodes from the stack (the right child is popped first), and set them as children of the operator node, then push the operator node onto the stack.
Returning the Tree's Root: Once all tokens have been processed, the stack will have one element left, which is the root of the constructed expression tree. This root node is then returned by the buildTree method.

The algorithms and patterns used here are typical for expression evaluation and tree construction problems. They elegantly apply the stack data structure for processing postfix notation and demonstrate the use of recursive methods like evaluate in the context of tree data structures.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's say we have the postfix expression: 3 4 2 * 1 5 - 2 3 ^ ^ / +. Here, ^ is an additional operator representing exponentiation for illustration purposes.

We want to construct a binary expression tree from this postfix expression and then evaluate the expression.

Initialization: We start with an empty stack.
Iteration: Processing the postfix tokens one by one:
- We encounter 3, which is a number; we create a node for 3 and push it onto the stack.
- Next is 4, another number; we create a node for 4 and push it onto the stack.
- Then comes 2, a number; we create a node for 2 and push it onto the stack.
- The next token is *, an operator. We pop 2 and 4 from the stack (in this order) and create an operator node * with 4 as the left child and 2 as the right child, then push it back onto the stack.
- We see 1, a number; we create a node for 1 and push it onto the stack.
- 5 follows, which is a number; we create a node for 5 and push it onto the stack.
- We encounter -, an operator. We pop 5 and 1 (in this order) and create an operator node - with 1 as the left child and 5 as the right child, then push it onto the stack.
- The token 2 is next, a number; we create a node for 2 and push it onto the stack.
- We encounter 3, a number; we create a node for 3 and push it onto the stack.
- The next token is ^, an operator. We pop 3 and 2 and create an operator node ^ with 2 as the left child and 3 as the right child, then push it onto the stack.
- Another ^, so we pop the two top nodes: the previously created exponentiation node and the subtraction node. We create a new exponentiation node, with the subtraction node as the left child and the exponentiation node as the right child, then push it onto the stack.
- We then see /, an operator. We pop the top two nodes: the exponentiation node we just created and the multiplication node earlier on. We create a division node / with the multiplication node as the left child and the exponentiation node as the right child and push it back onto the stack.
- The last token is +, another operator. We pop the division node and the initial 3 node and create an addition node + with 3 as the left child and the division node as the right child. This is the final operator, so it becomes the root of our tree.
Completion: At the end of the iteration, the stack has only the root node of our binary expression tree. The final tree structure can then be used to recursively evaluate the expression by invoking the evaluate method on the root node.

Following these steps, we have successfully constructed the binary expression tree that represents the given postfix expression, and we can now evaluate it to get the result of the expression.

Solution Implementation

1from abc import ABC, abstractmethod
2from typing import List
3
4# This abstract base class represents a node in an expression tree.
5class ExpressionNode(ABC):
6  
7    @abstractmethod
8    def evaluate(self) -> int:
9        """Evaluate the expression represented by the subtree rooted at this node."""
10        pass
11
12# Implementation of the ExpressionNode that can be an operand or an operator.
13class MyExpressionNode(ExpressionNode):
14  
15    def __init__(self, value):
16        self.value = value  # The value could be an operand or an operator.
17        self.left = None    # Pointer to the left child.
18        self.right = None   # Pointer to the right child.
19
20    def evaluate(self) -> int:
21        # If the value is a digit, return it as an integer.
22        if self.value.isdigit():
23            return int(self.value)
24      
25        # Otherwise, evaluate the left and right subtrees.
26        left_value = self.left.evaluate()
27        right_value = self.right.evaluate()
28      
29        # Perform the operation based on the operator this node represents.
30        if self.value == '+':
31            return left_value + right_value
32        elif self.value == '-':
33            return left_value - right_value
34        elif self.value == '*':
35            return left_value * right_value
36        elif self.value == '/':
37            return left_value // right_value
38
39# The TreeBuilder class constructs an expression tree from postfix notation.
40class TreeBuilder:
41  
42    def build_tree(self, postfix: List[str]) -> 'ExpressionNode':
43        """Builds the expression tree from the given postfix expression."""
44        stack = []
45        for symbol in postfix:
46            node = MyExpressionNode(symbol)
47            if not symbol.isdigit():
48                # If the symbol is an operator, pop the top two elements as its right and left children.
49                node.right = stack.pop()
50                node.left = stack.pop()
51            # Push the new node to the stack.
52            stack.append(node)
53      
54        # The last element on the stack is the root of the expression tree.
55        return stack[-1]
56
57# Example usage:
58# obj = TreeBuilder()
59# exp_tree = obj.build_tree(postfix)
60# answer = exp_tree.evaluate()
61

1abstract class Node {
2    // Field for the value
3    protected String value;
4    // Left and right children
5    protected Node left;
6    protected Node right;
7  
8    // Abstract method to evaluate the tree
9    public abstract int evaluate();
10};
11
12class MyNode extends Node {
13    // Constructor to create a new node with a given value
14    public MyNode(String value) {
15        this.value = value;
16    }
17
18    // Method to evaluate the node
19    public int evaluate() {
20        // If the node is a number, parse and return its integer value
21        if (isNumeric()) {
22            return Integer.parseInt(value);
23        }
24        // Otherwise, evaluate the left and right subtrees
25        int leftValue = left.evaluate();
26        int rightValue = right.evaluate();
27        // Perform the operation defined by the current node's value
28        switch (value) {
29            case "+": return leftValue + rightValue;
30            case "-": return leftValue - rightValue;
31            case "*": return leftValue * rightValue;
32            case "/": return leftValue / rightValue;
33            default: return 0; // If the operation is unknown
34        }
35    }
36
37    // Helper method to determine if the node's value is numeric
38    public boolean isNumeric() {
39        for (char c : value.toCharArray()) {
40            if (!Character.isDigit(c)) {
41                return false; // Not numeric if any character is not a digit
42            }
43        }
44        return true; // All characters are digits, hence numeric
45    }
46}
47
48class TreeBuilder {
49    // Method to build the expression tree from a postfix expression
50    Node buildTree(String[] postfix) {
51        Deque<MyNode> stack = new ArrayDeque<>();
52        for (String token : postfix) {
53            MyNode currentNode = new MyNode(token);
54            // If the token is an operator, pop two nodes and make them children
55            if (!currentNode.isNumeric()) {
56                currentNode.right = stack.pop();
57                currentNode.left = stack.pop();
58            }
59            // Push the current node onto the stack
60            stack.push(currentNode);
61        }
62        // The last node on the stack is the root of the expression tree
63        return stack.peek();
64    }
65};
66
67// Usage example
68// TreeBuilder object will be instantiated and called as follows:
69/*
70TreeBuilder treeBuilder = new TreeBuilder();
71Node expressionTree = treeBuilder.buildTree(postfix);
72int result = expressionTree.evaluate();
73*/
74

1/**
2 * Interface for the expression tree Node.
3 */
4class Node {
5public:
6    virtual ~Node() {}  // Virtual destructor for proper cleanup in derived classes
7    virtual int evaluate() const = 0;  // Pure virtual function for evaluating the expression
8
9protected:
10    std::string value;  // Value of the node
11    Node* left;         // Pointer to the left child
12    Node* right;        // Pointer to the right child
13};
14
15/**
16 * Concrete implementation of Node to represent an expression tree node.
17 */
18class MyNode : public Node {
19public:
20    // Constructor for operand nodes
21    MyNode(const std::string& value) {
22        this->value = value;
23        this->left = nullptr;
24        this->right = nullptr;
25    }
26
27    // Constructor for operator nodes with left and right children
28    MyNode(const std::string& value, Node* left, Node* right) {
29        this->value = value;
30        this->left = left;
31        this->right = right;
32    }
33
34    // Implementation of the evaluate function
35    int evaluate() const override {
36        // If the node is an operand, return its integer value
37        if (!(value == "+" || value == "-" || value == "*" || value == "/")) {
38            return std::stoi(value);
39        }
40
41        // Evaluate left and right subtrees
42        int leftValue = left->evaluate();
43        int rightValue = right->evaluate();
44
45        // Apply the operator to the evaluated subtree values
46        if (value == "+") return leftValue + rightValue;
47        if (value == "-") return leftValue - rightValue;
48        if (value == "*") return leftValue * rightValue;
49        if (value == "/") return leftValue / rightValue;
50
51        return 0;  // This should not happen if the input is a valid expression
52    }
53};
54
55/**
56 * Helper class to construct an expression tree from postfix notation.
57 */
58class TreeBuilder {
59public:
60    // Builds the expression tree from a postfix expression and returns its root
61    Node* buildTree(std::vector<std::string>& postfix) {
62        std::stack<MyNode*> stack;
63
64        for (const auto& token : postfix) {
65            MyNode* node;
66
67            // If token is an operator, pop two nodes and create a new operator node
68            if (token == "+" || token == "-" || token == "*" || token == "/") {
69                Node* rightChild = stack.top();
70                stack.pop();
71                Node* leftChild = stack.top();
72                stack.pop();
73
74                node = new MyNode(token, leftChild, rightChild);
75            } else {
76                // Token is an operand, create a new operand node
77                node = new MyNode(token);
78            }
79
80            // Push the new node onto the stack
81            stack.push(node);
82        }
83
84        // The root of the expression tree is the only node remaining in the stack
85        return stack.top();
86    }
87};
88

1// Node is an abstract type for expression tree nodes
2type Node = {
3  evaluate: () => number;
4  value: string;
5  left: Node | null;
6  right: Node | null;
7};
8
9// Constructor function for operand nodes, which only contain a value
10function createOperandNode(value: string): Node {
11  return {
12    value,
13    left: null,
14    right: null,
15    evaluate: function() {
16      // Since this is an operand node, simply return its integer value
17      return parseInt(this.value);
18    }
19  };
20}
21
22// Constructor function for operator nodes, which contain a value, and left and right children
23function createOperatorNode(value: string, left: Node, right: Node): Node {
24  return {
25    value,
26    left,
27    right,
28    evaluate: function() {
29      // Evaluate left and right subtrees
30      const leftValue = this.left!.evaluate();
31      const rightValue = this.right!.evaluate();
32
33      // Apply the appropriate operation based on the node's operator
34      switch (this.value) {
35        case '+':
36          return leftValue + rightValue;
37        case '-':
38          return leftValue - rightValue;
39        case '*':
40          return leftValue * rightValue;
41        case '/':
42          return leftValue / rightValue;
43        default:
44          // If the operator is unknown, throw an exception
45          throw new Error(`Unknown operator: ${this.value}`);
46      }
47    }
48  };
49}
50
51// Helper function that determines if a given token is an operator
52function isOperator(token: string): boolean {
53  return ['+', '-', '*', '/'].includes(token);
54}
55
56// Function that builds the expression tree from a postfix expression and returns its root
57function buildTree(postfix: string[]): Node {
58  const stack: Node[] = [];
59
60  postfix.forEach(token => {
61    let node: Node;
62
63    // If the token is an operator, pop two nodes and create a new operator node
64    if (isOperator(token)) {
65      const rightChild = stack.pop()!;
66      const leftChild = stack.pop()!;
67
68      node = createOperatorNode(token, leftChild, rightChild);
69    } else {
70      // The token is an operand, create a new operand node
71      node = createOperandNode(token);
72    }
73
74    // Push the new (either operand or operator) node onto the stack
75    stack.push(node);
76  });
77
78  // The root of the expression tree is the only node remaining in the stack
79  return stack[stack.length - 1];
80}
81
82// Example usage:
83// const postfix = ["3", "4", "+", "2", "*","7", "/"]; // Example postfix expression
84// const expressionTreeRoot = buildTree(postfix); // Builds the tree
85// console.log(expressionTreeRoot.evaluate()); // Evaluates the expression
86

Time and Space Complexity

The given code defines an expression tree with nodes representing operands or operators and implements methods to build the tree from postfix notation and evaluate the expression.

Time Complexity

The time complexity of the buildTree method is O(n), where n is the number of elements in the postfix list. Here is the reasoning:

Iterating through the postfix list of elements (n iterations): O(n)
Constructing nodes and pushing them onto the stack: O(1) per element
Popping nodes from the stack (at most twice for each operator): O(1) per element
Evaluating expressions in the evaluate method for each node involving an operator occurs once during the final evaluation after the tree construction.

For the evaluate method, assuming it is called once after the tree is constructed, its time complexity is O(m), with m being the total number of nodes in the expression tree. In the worst case, m could be similar to n, so it could also be considered O(n) for the tree traversal. Every node in the expression tree will be evaluated exactly once.

Hence, the overall time complexity of building and evaluating the expression tree is O(n).

Space Complexity

The space complexity of the program is primarily determined by the stack that holds the intermediate nodes and the space required for the expression tree itself:

Stack used for construction (buildTree): O(n) because at worst, it will contain all operands before starting to attach nodes to operators.
Tree (MyNode): O(n) considering that a new MyNode object is created for every element in the postfix list.

Thus, the overall space complexity is O(n), assuming that the space required to store the tree and stack is the dominant factor (not taking into constant space such as local variables in the evaluate which is negligible).

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

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

Is the following code DFS or BFS?

void search(Node root) {
  if (!root) return;
  visit(root);
  root.visited = true;
  for (Node node in root.adjacent) {
    if (!node.visited) {
      search(node);
    }
  }
}

Depth First Search

Breadth First Search

I don’t know