The "Build Binary Expression Tree From Infix Expression" problem asks you to construct a binary expression tree from a given infix mathematical expression. An infix expression is a string containing numbers, operators (+, -, *, /), and parentheses, written in the usual way (e.g., 2*(3+4)).
The goal is to parse this string and build a binary tree where:
The problem guarantees that the input expression is valid and contains only non-negative integers, the operators +, -, *, /, and parentheses ( ). There is exactly one valid way to parse the expression, and you should not reuse or rearrange elements.
To solve this problem, we need to convert an infix expression (which is how we usually write math) into a binary tree that represents the order of operations. The key challenge is respecting operator precedence (e.g., multiplication before addition) and grouping via parentheses.
A brute-force approach might try to recursively split the string at every possible operator, but this quickly becomes inefficient and complicated, especially with nested parentheses and operator precedence.
Instead, we can use a stack-based algorithm, much like the Shunting Yard algorithm or the process used to convert infix expressions to postfix notation. By using two stacks—one for operators and one for tree nodes—we can process the expression from left to right, building up the tree as we go. This approach efficiently handles precedence and grouping, and is well-suited for constructing the binary expression tree.
Let's break down the solution step by step:
op_stack).node_stack).node_stack.op_stack with higher or equal precedence and build subtrees, then push the current operator.(, push it onto op_stack.), pop operators and build subtrees until we find the matching (.node_stack is the root of the binary expression tree.This method ensures that the tree structure correctly reflects operator precedence and parentheses, just like how a calculator would evaluate the expression.
Let's walk through the process with the example input: 2*(3+4)
2: Push a leaf node with value 2 onto node_stack.*: Push * onto op_stack.(: Push ( onto op_stack.3: Push a leaf node with value 3 onto node_stack.+: Push + onto op_stack (since ( is on top, no popping).4: Push a leaf node with value 4 onto node_stack.):
+ from op_stack, pop two nodes (3 and 4), build + node with these as children, push onto node_stack.( from op_stack.* from op_stack, pop two nodes (2 and (3+4)), build * node, push onto node_stack.*, with left child 2 and right child + (which has children 3 and 4).The resulting tree structure is:
Brute-force approach: If you tried every possible way to parenthesize or split the expression, the time complexity would be exponential, as the number of ways to fully parenthesize grows rapidly with input size.
Optimized stack-based approach:
To build a binary expression tree from an infix string, we use a stack-based algorithm inspired by the Shunting Yard method. By carefully managing operator precedence and parentheses with two stacks, we efficiently construct the tree in a single pass. This approach is both elegant and efficient, handling all valid infix expressions robustly.
# Definition for a binary tree node.
class Node:
def __init__(self, val, left=None, right=None):
self.val = val # operator or operand (str)
self.left = left
self.right = right
class Solution:
def buildTree(self, s: str) -> 'Node':
def precedence(op):
if op in ('+', '-'):
return 1
if op in ('*', '/'):
return 2
return 0
op_stack = []
node_stack = []
i = 0
n = len(s)
while i < n:
if s[i] == ' ':
i += 1
continue
if s[i] == '(':
op_stack.append('(')
i += 1
elif s[i].isdigit():
num = ''
while i < n and s[i].isdigit():
num += s[i]
i += 1
node_stack.append(Node(num))
elif s[i] == ')':
while op_stack and op_stack[-1] != '(':
op = op_stack.pop()
right = node_stack.pop()
left = node_stack.pop()
node_stack.append(Node(op, left, right))
op_stack.pop() # pop '('
i += 1
else: # operator
while (op_stack and op_stack[-1] != '(' and
precedence(op_stack[-1]) >= precedence(s[i])):
op = op_stack.pop()
right = node_stack.pop()
left = node_stack.pop()
node_stack.append(Node(op, left, right))
op_stack.append(s[i])
i += 1
while op_stack:
op = op_stack.pop()
right = node_stack.pop()
left = node_stack.pop()
node_stack.append(Node(op, left, right))
return node_stack[-1]
/**
* Definition for a binary tree node.
* struct Node {
* string val;
* Node *left;
* Node *right;
* Node(string x) : val(x), left(NULL), right(NULL) {}
* Node(string x, Node* l, Node* r) : val(x), left(l), right(r) {}
* };
*/
class Solution {
public:
int precedence(char op) {
if (op == '+' || op == '-') return 1;
if (op == '*' || op == '/') return 2;
return 0;
}
Node* buildTree(string s) {
vector<char> op_stack;
vector<Node*> node_stack;
int n = s.size();
int i = 0;
while (i < n) {
if (s[i] == ' ') {
i++;
continue;
}
if (s[i] == '(') {
op_stack.push_back('(');
i++;
} else if (isdigit(s[i])) {
string num = "";
while (i < n && isdigit(s[i])) {
num += s[i++];
}
node_stack.push_back(new Node(num));
} else if (s[i] == ')') {
while (!op_stack.empty() && op_stack.back() != '(') {
char op = op_stack.back(); op_stack.pop_back();
Node* right = node_stack.back(); node_stack.pop_back();
Node* left = node_stack.back(); node_stack.pop_back();
node_stack.push_back(new Node(string(1, op), left, right));
}
op_stack.pop_back(); // pop '('
i++;
} else { // operator
while (!op_stack.empty() && op_stack.back() != '(' &&
precedence(op_stack.back()) >= precedence(s[i])) {
char op = op_stack.back(); op_stack.pop_back();
Node* right = node_stack.back(); node_stack.pop_back();
Node* left = node_stack.back(); node_stack.pop_back();
node_stack.push_back(new Node(string(1, op), left, right));
}
op_stack.push_back(s[i]);
i++;
}
}
while (!op_stack.empty()) {
char op = op_stack.back(); op_stack.pop_back();
Node* right = node_stack.back(); node_stack.pop_back();
Node* left = node_stack.back(); node_stack.pop_back();
node_stack.push_back(new Node(string(1, op), left, right));
}
return node_stack.back();
}
};
/**
* Definition for a binary tree node.
* public class Node {
* public String val;
* public Node left, right;
* public Node(String val) { this.val = val; }
* public Node(String val, Node left, Node right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
private int precedence(char op) {
if (op == '+' || op == '-') return 1;
if (op == '*' || op == '/') return 2;
return 0;
}
public Node buildTree(String s) {
Stack<Character> opStack = new Stack<>();
Stack<Node> nodeStack = new Stack<>();
int n = s.length();
int i = 0;
while (i < n) {
if (s.charAt(i) == ' ') {
i++;
continue;
}
if (s.charAt(i) == '(') {
opStack.push('(');
i++;
} else if (Character.isDigit(s.charAt(i))) {
StringBuilder num = new StringBuilder();
while (i < n && Character.isDigit(s.charAt(i))) {
num.append(s.charAt(i++));
}
nodeStack.push(new Node(num.toString()));
} else if (s.charAt(i) == ')') {
while (!opStack.isEmpty() && opStack.peek() != '(') {
char op = opStack.pop();
Node right = nodeStack.pop();
Node left = nodeStack.pop();
nodeStack.push(new Node(String.valueOf(op), left, right));
}
opStack.pop(); // pop '('
i++;
} else { // operator
while (!opStack.isEmpty() && opStack.peek() != '(' &&
precedence(opStack.peek()) >= precedence(s.charAt(i))) {
char op = opStack.pop();
Node right = nodeStack.pop();
Node left = nodeStack.pop();
nodeStack.push(new Node(String.valueOf(op), left, right));
}
opStack.push(s.charAt(i));
i++;
}
}
while (!opStack.isEmpty()) {
char op = opStack.pop();
Node right = nodeStack.pop();
Node left = nodeStack.pop();
nodeStack.push(new Node(String.valueOf(op), left, right));
}
return nodeStack.peek();
}
}
/**
* Definition for a binary tree node.
* function Node(val, left, right) {
* this.val = val;
* this.left = left || null;
* this.right = right || null;
* }
*/
var buildTree = function(s) {
function precedence(op) {
if (op === '+' || op === '-') return 1;
if (op === '*' || op === '/') return 2;
return 0;
}
let opStack = [];
let nodeStack = [];
let i = 0, n = s.length;
while (i < n) {
if (s[i] === ' ') {
i++;
continue;
}
if (s[i] === '(') {
opStack.push('(');
i++;
} else if (/\d/.test(s[i])) {
let num = '';
while (i < n && /\d/.test(s[i])) {
num += s[i++];
}
nodeStack.push(new Node(num));
} else if (s[i] === ')') {
while (opStack.length && opStack[opStack.length-1] !== '(') {
let op = opStack.pop();
let right = nodeStack.pop();
let left = nodeStack.pop();
nodeStack.push(new Node(op, left, right));
}
opStack.pop(); // pop '('
i++;
} else { // operator
while (opStack.length && opStack[opStack.length-1] !== '(' &&
precedence(opStack[opStack.length-1]) >= precedence(s[i])) {
let op = opStack.pop();
let right = nodeStack.pop();
let left = nodeStack.pop();
nodeStack.push(new Node(op, left, right));
}
opStack.push(s[i]);
i++;
}
}
while (opStack.length) {
let op = opStack.pop();
let right = nodeStack.pop();
let left = nodeStack.pop();
nodeStack.push(new Node(op, left, right));
}
return nodeStack[nodeStack.length-1];
};