# Build Binary Expression Tree From Infix Expression

This page explains Java solution to problem `Build Binary Expression Tree From Infix Expression` using `Tree` data structure.

## Problem Statement

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.

Example 1:

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

Example 2:

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

Example 3:

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

## Solution

If you have any suggestions in below code, please create a pull request by clicking here.
``````
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) {
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 == '+') {
}
else if(prevSign == '*' || prevSign == '/') {
TreeNode prevOperand = deque.pollLast();
TreeNode signNode = new TreeNode(prevSign);
signNode.left = prevOperand;
signNode.right = currentOperand;
}
else {
}
}
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;
}
return deque.pollLast();
}
}

``````

## Time Complexity

O(N) Where
N is number of characters in an input String s

## Space Complexity

O(N) Where
N is number of characters in an input String s