# LeetCode 536: Construct Binary Tree from String

## Problem Restatement

We are given a string representing a binary tree.

The string format is:

```text
node(left_subtree)(right_subtree)
```

Each node starts with an integer value.

If a node has children, the left subtree appears first inside parentheses.

The right subtree appears second inside another pair of parentheses.

We need to reconstruct the binary tree and return its root.

The string may contain negative integers.

## Input and Output

| Item | Meaning |
|---|---|
| Input | A string representing a binary tree |
| Output | The root of the reconstructed binary tree |
| Node values | Integers, including negatives |
| Empty tree | Empty string returns `None` |

Function shape:

```python
def str2tree(s: str) -> Optional[TreeNode]:
    ...
```

## Examples

Consider:

```python
s = "4(2(3)(1))(6(5))"
```

The root value is:

```python
4
```

The left subtree is:

```python
2(3)(1)
```

The right subtree is:

```python
6(5)
```

So the constructed tree is:

```text
        4
       / \
      2   6
     / \  /
    3  1 5
```

Another example:

```python
s = "1(2)(3)"
```

Tree:

```text
    1
   / \
  2   3
```

A negative example:

```python
s = "-4(2)(3)"
```

Tree:

```text
   -4
   / \
  2   3
```

## First Thought: Parse Character by Character

The string contains nested parentheses, which naturally suggests recursion.

A node is always followed by:

```text
(left subtree)
(right subtree)
```

if children exist.

So instead of manually managing many substring cases, we can recursively parse:

1. The node value.
2. The left subtree.
3. The right subtree.

The recursive call naturally handles nested structure.

## Key Insight

Every subtree in the string is itself a valid tree string.

For example:

```python
"2(3)(1)"
```

is a complete subtree.

So the problem has recursive structure.

The main challenge is determining where a subtree ends.

Parentheses matching solves this.

When parsing:

```text
(...)
```

we track balance:

| Character | Action |
|---|---|
| `(` | `+1` |
| `)` | `-1` |

When balance returns to `0`, we found the matching closing parenthesis.

## Algorithm

For a string `s`:

1. If `s` is empty, return `None`.
2. Parse the root integer from the beginning.
3. Create the root node.
4. If no parentheses remain, return the node.
5. Find the substring for the left subtree.
6. Recursively build the left child.
7. If another subtree exists, recursively build the right child.
8. Return the root.

## Correctness

The algorithm first parses the root value, which is always the prefix integer of the current subtree string.

After parsing the value, any remaining content consists of zero, one, or two parenthesized subtree strings. The first parenthesized substring represents the left subtree. The optional second parenthesized substring represents the right subtree.

The parenthesis balance scan finds the exact boundary of the left subtree because it tracks nested parentheses correctly. When the balance returns to zero, the current closing parenthesis matches the opening parenthesis of the subtree.

The recursive call receives exactly the substring corresponding to that subtree. By induction, the recursive call correctly constructs the subtree represented by that substring.

The same logic applies to the right subtree.

Therefore, the constructed node has the correct value, correct left child, and correct right child. Since recursion processes every subtree correctly, the entire tree is reconstructed correctly.

## Complexity

Let `n = len(s)`.

| Metric | Value | Why |
|---|---:|---|
| Time | `O(n^2)` worst case | Substring creation and repeated scans |
| Space | `O(n)` | Recursion depth and substrings |

The repeated substring slicing causes the quadratic worst case.

A later section shows an optimized index-based parser with linear complexity.

## Implementation

```python
from typing import Optional

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def str2tree(self, s: str) -> Optional[TreeNode]:
        if not s:
            return None

        i = 0

        while i < len(s) and (s[i] == "-" or s[i].isdigit()):
            i += 1

        root_value = int(s[:i])
        root = TreeNode(root_value)

        if i == len(s):
            return root

        start = i
        balance = 0

        for j in range(start, len(s)):
            if s[j] == "(":
                balance += 1
            elif s[j] == ")":
                balance -= 1

            if balance == 0:
                root.left = self.str2tree(s[start + 1:j])
                i = j + 1
                break

        if i < len(s):
            root.right = self.str2tree(s[i + 1:-1])

        return root
```

## Code Explanation

We first handle the empty string:

```python
if not s:
    return None
```

Then we parse the root integer.

```python
while i < len(s) and (s[i] == "-" or s[i].isdigit()):
    i += 1
```

This supports both positive and negative integers.

For example:

```python
"-42"
```

After parsing:

```python
root_value = int(s[:i])
```

we create the node.

If the string ends here, the node has no children:

```python
if i == len(s):
    return root
```

Otherwise, we locate the left subtree boundaries using parenthesis balance.

```python
if s[j] == "(":
    balance += 1
elif s[j] == ")":
    balance -= 1
```

When:

```python
balance == 0
```

the left subtree substring is complete.

We recursively build it:

```python
root.left = self.str2tree(s[start + 1:j])
```

Then we parse the optional right subtree:

```python
root.right = self.str2tree(s[i + 1:-1])
```

## Optimized Index-Based Parser

The previous solution repeatedly creates substrings.

We can avoid this by parsing directly with a shared index.

This reduces the complexity to `O(n)`.

```python
from typing import Optional

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def str2tree(self, s: str) -> Optional[TreeNode]:
        self.i = 0

        def parse() -> Optional[TreeNode]:
            if self.i >= len(s):
                return None

            sign = 1

            if s[self.i] == "-":
                sign = -1
                self.i += 1

            num = 0

            while self.i < len(s) and s[self.i].isdigit():
                num = num * 10 + int(s[self.i])
                self.i += 1

            node = TreeNode(sign * num)

            if self.i < len(s) and s[self.i] == "(":
                self.i += 1
                node.left = parse()
                self.i += 1

            if self.i < len(s) and s[self.i] == "(":
                self.i += 1
                node.right = parse()
                self.i += 1

            return node

        if not s:
            return None

        return parse()
```

This version scans the string once from left to right.

## Testing

```python
def tree_to_tuple(root):
    if not root:
        return None

    return (
        root.val,
        tree_to_tuple(root.left),
        tree_to_tuple(root.right),
    )

def run_tests():
    s = Solution()

    root = s.str2tree("4(2(3)(1))(6(5))")
    assert tree_to_tuple(root) == (
        4,
        (2, (3, None, None), (1, None, None)),
        (6, (5, None, None), None),
    )

    root = s.str2tree("1(2)(3)")
    assert tree_to_tuple(root) == (
        1,
        (2, None, None),
        (3, None, None),
    )

    root = s.str2tree("-4(2)(3)")
    assert tree_to_tuple(root) == (
        -4,
        (2, None, None),
        (3, None, None),
    )

    root = s.str2tree("")
    assert root is None

    root = s.str2tree("7")
    assert tree_to_tuple(root) == (
        7,
        None,
        None,
    )

    print("all tests passed")

run_tests()
```

| Test | Why |
|---|---|
| Nested tree | Checks recursive subtree parsing |
| Two children | Standard balanced case |
| Negative root | Checks sign parsing |
| Empty string | Checks null tree |
| Single node | Checks base case |