Watch the video solution for Build Binary Expression Tree From Infix Expression, a hard level problem involving String, Stack, Tree. This walkthrough by AlitaCode has 14 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
A binary expression tree is a kind of binary tree used to represent arithmetic expressions. Each node of a binary expression tree has either zero or two children. Leaf nodes (nodes with 0 children) correspond to operands (numbers), and internal nodes (nodes with 2 children) correspond to the operators '+' (addition), '-' (subtraction), '*' (multiplication), and '/' (division).
For each internal node with operator o, the infix expression it represents is (A o B), where A is the expression the left subtree represents and B is the expression the right subtree represents.
You are given a string s, an infix expression containing operands, the operators described above, and parentheses '(' and ')'.
Return any valid binary expression tree, whose in-order traversal reproduces s after omitting the parenthesis from it.
Please note that order of operations applies in s. That is, expressions in parentheses are evaluated first, and multiplication and division happen before addition and subtraction.
Operands must also appear in the same order in both s and the in-order traversal of the tree.
Example 1:
Input: s = "3*4-2*5" Output: [-,*,*,3,4,2,5] Explanation: The tree above is the only valid tree whose inorder traversal produces s.
Example 2:
Input: s = "2-3/(5*2)+1" Output: [+,-,1,2,/,null,null,null,null,3,*,null,null,5,2] Explanation: The inorder traversal of the tree above is 2-3/5*2+1 which is the same as s without the parenthesis. The tree also produces the correct result and its operands are in the same order as they appear in s. The tree below is also a valid binary expression tree with the same inorder traversal as s, but it not a valid answer because it does not evaluate to the same value.The third tree below is also not valid. Although it produces the same result and is equivalent to the above trees, its inorder traversal does not produce s and its operands are not in the same order as s.
Example 3:
Input: s = "1+2+3+4+5" Output: [+,+,5,+,4,null,null,+,3,null,null,1,2] Explanation: The tree [+,+,5,+,+,null,null,1,2,3,4] is also one of many other valid trees.
Constraints:
1 <= s.length <= 100s consists of digits and the characters '(', ')', '+', '-', '*', and '/'.s are exactly 1 digit.s is a valid expression.Problem Overview: You receive an infix arithmetic expression as a string containing digits, operators (+, -, *, /), and parentheses. The goal is to convert that expression into a binary expression tree where operators become internal nodes and operands become leaf nodes while preserving operator precedence and parentheses.
The challenge is parsing the infix order correctly. Operators with higher precedence must appear deeper in the tree, and parentheses override normal precedence. A correct solution mimics how compilers parse expressions.
Approach 1: Recursive Split by Lowest Precedence (O(n²) time, O(n) space)
Scan the current substring and locate the operator with the lowest precedence that is not inside parentheses. That operator becomes the root of the current subtree. Recursively build the left subtree from the substring before the operator and the right subtree from the substring after it. Parentheses are handled by tracking depth during the scan. This method mirrors how infix expressions are evaluated but repeatedly rescans substrings, leading to O(n²) worst‑case time complexity. Space complexity is O(n) due to recursion and the resulting binary tree.
Approach 2: Two Stacks (Shunting‑Yard Style) Tree Construction (O(n) time, O(n) space)
The optimal solution processes the expression once using two stacks: one for operand nodes and one for operators. Iterate through the string. When you see a number, create a tree node and push it to the operand stack. When you encounter an operator, resolve any operators on the stack with higher or equal precedence by popping them and forming tree nodes. Parentheses temporarily delay evaluation until the closing parenthesis appears. Each time an operator is resolved, pop two operand nodes, attach them as children, and push the resulting node back.
This method follows the classic infix parsing technique used in compilers. Every character is processed once, and each operator is pushed and popped at most once. The result is O(n) time and O(n) space. The stacks explicitly model expression evaluation order and are typically implemented using a stack data structure.
Recommended for interviews: The stack-based parsing approach is the expected answer. It demonstrates understanding of operator precedence, expression parsing, and tree construction in linear time. Mentioning the recursive split approach first can show conceptual understanding, but implementing the stack-based O(n) solution proves stronger algorithmic skill.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Recursive split by lowest precedence | O(n²) | O(n) | Good for understanding expression structure or quick prototypes |
| Two stacks (operator + operand) parsing | O(n) | O(n) | Optimal solution for interviews and production parsing |