> For the complete documentation index, see [llms.txt](https://jaywin.gitbook.io/leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://jaywin.gitbook.io/leetcode/solutions/1597-build-binary-expression-tree-from-infix-expression.md).

# 1597. Build Binary Expression Tree From Infix Expression

<https://leetcode.com/problems/build-binary-expression-tree-from-infix-expression>

## Description

A [**binary expression tree**](https://en.wikipedia.org/wiki/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**](https://en.wikipedia.org/wiki/Infix_notation) 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***](https://en.wikipedia.org/wiki/Tree_traversal#In-order_\(LNR\)) *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:**

![](https://assets.leetcode.com/uploads/2020/10/02/ex1-4.png)

```
**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:**

![](https://assets.leetcode.com/uploads/2020/10/02/ex1-2.png)

```
**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.
![](https://assets.leetcode.com/uploads/2020/10/02/ex1-1.png)
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.
![](https://assets.leetcode.com/uploads/2020/10/02/ex1-3.png)
```

**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 <= 1000`
* `s` consists of digits and the characters `'+'`, `'-'`, `'*'`, and `'/'`.
* Operands in `s` are **exactly** 1 digit.
* It is guaranteed that `s` is a valid expression.

## ac

```java
```


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://jaywin.gitbook.io/leetcode/solutions/1597-build-binary-expression-tree-from-infix-expression.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.