LeetCode 1628: Design an Expression Tree With Evaluate Function Solution

Master LeetCode problem 1628 (Design an Expression Tree With Evaluate Function), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

1628. Design an Expression Tree With Evaluate Function

Medium

Array Math Stack Tree Design Binary Tree

Problem Explanation

Explanation:

To design an Expression Tree with an evaluate function, we can use a binary tree where each node represents an operand or an operator. We can construct the tree recursively by following the order of operations (parentheses, multiplication, division, addition, and subtraction).

For each operator node, we can recursively evaluate its left and right subtrees and then perform the corresponding operation. The evaluate function will return the result of the expression represented by the tree.

Algorithm:

Define a TreeNode class to represent each node of the expression tree.
Use a stack to parse the input expression and construct the expression tree.
Define a recursive evaluate function to calculate the result of the expression.

Time Complexity:

The time complexity for constructing the expression tree and evaluating the expression is O(n), where n is the number of nodes in the tree.

Space Complexity:

The space complexity is also O(n) due to the stack used for constructing the expression tree.

: :

Solution Code

class TreeNode {
    String val;
    TreeNode left;
    TreeNode right;

    public TreeNode(String val) {
        this.val = val;
    }

    public int evaluate() {
        if (val.equals("+")) {
            return left.evaluate() + right.evaluate();
        } else if (val.equals("-")) {
            return left.evaluate() - right.evaluate();
        } else if (val.equals("*")) {
            return left.evaluate() * right.evaluate();
        } else if (val.equals("/")) {
            return left.evaluate() / right.evaluate();
        } else {
            return Integer.parseInt(val);
        }
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 1628 (Design an Expression Tree With Evaluate Function)?

This page provides optimized solutions for LeetCode problem 1628 (Design an Expression Tree With Evaluate Function) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 1628 (Design an Expression Tree With Evaluate Function)?

The time complexity for LeetCode 1628 (Design an Expression Tree With Evaluate Function) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 1628 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 1628 in Java, C++, or Python.

Back to LeetCode Solutions