LeetCode 1597: Build Binary Expression Tree From Infix Expression Solution

Master LeetCode problem 1597 (Build Binary Expression Tree From Infix Expression), a hard 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.

1597. Build Binary Expression Tree From Infix Expression

Hard

String Stack Tree Binary Tree

Problem Explanation

Explanation

To build a binary expression tree from an infix expression, we can use the shunting yard algorithm. The shunting yard algorithm converts infix expressions to postfix notation, which can then be used to build the binary expression tree.

The steps involved in the algorithm are as follows:

Initialize an empty stack for operators (opStack) and an empty list for the postfix expression (postfixList).
Iterate through the infix expression from left to right:
- If the current token is an operand, add it to the postfix list.
- If the current token is an operator:
  - While the opStack is not empty and the precedence of the current token is less than or equal to the precedence of the top of the opStack, pop operators from the opStack and add them to the postfix list.
  - Push the current operator onto the opStack.
After iterating through the infix expression, pop any remaining operators from the opStack and add them to the postfix list.
Build the binary expression tree from the postfix expression using a stack:
- For each token in the postfix expression:
  - If the token is an operand, push it onto the stack.
  - If the token is an operator, pop the top two operands from the stack, create a new node with the operator as the value and the two operands as its left and right children, and push this node back onto the stack.
- The final node on the stack is the root of the binary expression tree.

The time complexity of this algorithm is O(n) where n is the length of the infix expression, and the space complexity is O(n) for the stack and postfix list.

Solution Code

class Solution {
    public Node expTree(String s) {
        Stack<Node> stack = new Stack<>();
        Stack<Character> opStack = new Stack<>();
        
        for (char c : s.toCharArray()) {
            if (Character.isDigit(c)) {
                stack.push(new Node(c));
            } else if (c == '(') {
                opStack.push(c);
            } else if (c == ')') {
                while (!opStack.isEmpty() && opStack.peek() != '(') {
                    processOperator(stack, opStack.pop());
                }
                opStack.pop(); // Pop the '('
            } else if (isOperator(c)) {
                while (!opStack.isEmpty() && precedence(opStack.peek()) >= precedence(c)) {
                    processOperator(stack, opStack.pop());
                }
                opStack.push(c);
            }
        }
        
        while (!opStack.isEmpty()) {
            processOperator(stack, opStack.pop());
        }
        
        return stack.pop();
    }
    
    private boolean isOperator(char c) {
        return c == '+' || c == '-' || c == '*' || c == '/';
    }
    
    private int precedence(char op) {
        if (op == '+' || op == '-') {
            return 1;
        } else if (op == '*' || op == '/') {
            return 2;
        }
        return 0;
    }
    
    private void processOperator(Stack<Node> stack, char op) {
        Node right = stack.pop();
        Node left = stack.pop();
        Node newNode = new Node(op);
        newNode.left = left;
        newNode.right = right;
        stack.push(newNode);
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 1597 (Build Binary Expression Tree From Infix Expression)?

This page provides optimized solutions for LeetCode problem 1597 (Build Binary Expression Tree From Infix Expression) 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 1597 (Build Binary Expression Tree From Infix Expression)?

The time complexity for LeetCode 1597 (Build Binary Expression Tree From Infix Expression) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 1597 on DevExCode?

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

Back to LeetCode Solutions