LeetCode 536: Construct Binary Tree from String

Problem Restatement

We are given a string representing a binary tree.

The string format is:

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:

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

Examples

Consider:

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

The root value is:

The left subtree is:

2(3)(1)

The right subtree is:

6(5)

So the constructed tree is:

Another example:

s = "1(2)(3)"

Tree:

    1
   / \
  2   3

A negative example:

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

Tree:

   -4
   / \
  2   3

First Thought: Parse Character by Character

The string contains nested parentheses, which naturally suggests recursion.

A node is always followed by:

(left subtree)
(right subtree)

if children exist.

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

The node value.
The left subtree.
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:

"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:

(...)

we track balance:

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

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

Algorithm

For a string s:

If s is empty, return None.
Parse the root integer from the beginning.
Create the root node.
If no parentheses remain, return the node.
Find the substring for the left subtree.
Recursively build the left child.
If another subtree exists, recursively build the right child.
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

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:

if not s:
    return None

Then we parse the root integer.

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

This supports both positive and negative integers.

For example:

"-42"

After parsing:

root_value = int(s[:i])

we create the node.

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

if i == len(s):
    return root

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

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

When:

balance == 0

the left subtree substring is complete.

We recursively build it:

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

Then we parse the optional right subtree:

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).

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

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