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
postfixtokens. - 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.
Which of the following is the prefix sum of array [1, 2, 3, 4, 5]?
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
MyNodethat implements the abstract base classNode. TheMyNodeclass 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
evaluateMethod: In theMyNodeclass, theevaluatemethod 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
buildTreemethod of theTreeBuilderclass takes an array ofpostfixtokens 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
MyNodewith the operand as its value and push it on the stack. - If it's an operator, create a new
MyNodewith 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.
- If it's an operand, create a new
-
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
buildTreemethod.
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.
In a binary min heap, the minimum element can be found in:
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 for3and push it onto the stack. - Next is
4, another number; we create a node for4and push it onto the stack. - Then comes
2, a number; we create a node for2and push it onto the stack. - The next token is
*, an operator. We pop2and4from the stack (in this order) and create an operator node*with4as the left child and2as the right child, then push it back onto the stack. - We see
1, a number; we create a node for1and push it onto the stack. 5follows, which is a number; we create a node for5and push it onto the stack.- We encounter
-, an operator. We pop5and1(in this order) and create an operator node-with1as the left child and5as the right child, then push it onto the stack. - The token
2is next, a number; we create a node for2and push it onto the stack. - We encounter
3, a number; we create a node for3and push it onto the stack. - The next token is
^, an operator. We pop3and2and create an operator node^with2as the left child and3as 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 initial3node and create an addition node+with3as the left child and the division node as the right child. This is the final operator, so it becomes the root of our tree.
- We encounter
-
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
evaluatemethod 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()
611abstract 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*/
741/**
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};
881// 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
86Which of these pictures shows the visit order of a depth-first search?
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
postfixlist of elements (niterations):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
evaluatemethod 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 newMyNodeobject is created for every element in thepostfixlist.
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.
Which of the following is the prefix sum of array [1, 2, 3, 4, 5]?
Recommended Readings
Stack Intro Imagine you have a pile of books on your desk If you want to add a new book you place it on top If you want to read a book you take it from the top And if you simply want to see which book is on the top you
Everything About Trees A tree is a type of graph data structure composed of nodes and edges Its main properties are It is acyclic doesn't contain any cycles There exists a path from the root to any node Has N 1 edges where N is the number of nodes in the tree and
Math for Technical Interviews How much math do I need to know for technical interviews The short answer is about high school level math Computer science is often associated with math and some universities even place their computer science department under the math faculty However the reality is that you
Got a question? Ask the Teaching Assistant anything you don't understand.
Still not clear? Ask in the Forum, Discord or Submit the part you don't understand to our editors.