This page explains Java solution to problem `Build Binary Expression Tree From Infix Expression`

using `Tree`

data structure.

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 that 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, which its in-order traversal reproduces `s`

after omitting the parenthesis from it (see examples below).

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.

Input: "2-3/(5*2)+1"Output: [+,-,1,2,/,null,null,null,null,3,*,null,null,5,2]

Input: "3*4-2*5"Output: [-,*,*,3,4,2,5]

Input: "1+2+3+4+5"Output: [+,+,5,+,4,null,null,+,3,null,null,1,2]

```
package com.vc.hard;
import java.util.*;
/**
* Definition for a binary tree node.
* public class TreeNode {
* public int val;
* public TreeNode left;
* public TreeNode right;
* public TreeNode(int x) { val = x; }
* }
*/
class BuildBinaryExpressionTreeFromInfixExpression {
public TreeNode expTree(String s) {
Queue<Character> q = new LinkedList<>();
for(int i = 0; i < s.length(); i++) {
q.offer(s.charAt(i));
}
return helper(q);
}
private TreeNode helper(Queue<Character> q) {
ArrayDeque<TreeNode> deque = new ArrayDeque<>();
char prevSign = ' ';
while(!q.isEmpty()) {
char ch = q.poll();
if(Character.isDigit(ch) || ch == '(') {
TreeNode currentOperand = ch == '(' ? helper(q) : new TreeNode(ch);
if(prevSign == '-' || prevSign == '+') {
deque.addLast(new TreeNode(prevSign));
deque.addLast(currentOperand);
}
else if(prevSign == '*' || prevSign == '/') {
TreeNode prevOperand = deque.pollLast();
TreeNode signNode = new TreeNode(prevSign);
signNode.left = prevOperand;
signNode.right = currentOperand;
deque.addLast(signNode);
}
else {
deque.addLast(currentOperand);
}
}
else if(ch == ')') break;
else prevSign = ch;
}
while(deque.size() > 1) {
TreeNode first = deque.pollFirst();
TreeNode operator = deque.pollFirst();
TreeNode second = deque.pollFirst();
operator.left = first;
operator.right = second;
deque.addFirst(operator);
}
return deque.pollLast();
}
}
```

O(N) Where

N is number of characters in an input String s

O(N) Where

N is number of characters in an input String s