LeetCode 536 - Construct Binary Tree from String

This problem asks us to reconstruct a binary tree from a specially formatted string representation. The input string contains integer values and parentheses. Every integer represents a tree node, and parentheses represent child subtrees.

leetcodemediumstringstacktreedepth-first-searchbinary-tree

LeetCode Problem 536

Difficulty: 🟡 Medium
Topics: String, Stack, Tree, Depth-First Search, Binary Tree

Solution

Problem Understanding

This problem asks us to reconstruct a binary tree from a specially formatted string representation.

The input string contains integer values and parentheses. Every integer represents a tree node, and parentheses represent child subtrees. The structure follows a recursive pattern:

  • A node value appears first.
  • If the node has children, they are enclosed in parentheses.
  • The first parenthesized subtree is always the left child.
  • The second parenthesized subtree, if present, is the right child.

For example:

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

represents this tree:

        4
      /   \
     2     6
    / \   /
   3   1 5

The output should be the root node of the constructed binary tree.

The constraints tell us several important things:

  • The string length can be as large as 3 * 10^4, so inefficient repeated parsing or substring creation can become expensive.

  • The string contains only:

  • digits

  • -

  • (

  • )

  • Negative values are allowed.

  • The input is guaranteed to be valid.

An empty string represents an empty tree, so we should return None in Python or nil in Go.

There are several edge cases that can easily cause bugs:

  • Empty input string.
  • Negative numbers such as "-4".
  • Nodes with only a left child.
  • Deeply nested trees.
  • Multi digit values like "123".
  • Correctly associating children with parents while traversing nested parentheses.

A naive parser can easily lose track of which node is currently active, especially when recursive subtree boundaries overlap.

Approaches

Brute Force Approach

A brute force solution recursively searches for matching parentheses and repeatedly slices substrings to construct left and right subtrees.

The general idea is:

  1. Parse the current node value.
  2. Find the substring corresponding to the left subtree by locating matching parentheses.
  3. Recursively parse that substring.
  4. Repeat for the right subtree.

This approach works because the tree structure is explicitly encoded in the parentheses. If we correctly identify subtree boundaries, recursion naturally reconstructs the original tree.

However, repeated substring operations are expensive. Every recursive call may create new substrings, and matching parentheses repeatedly scans parts of the string again and again.

In the worst case, such as a highly skewed tree:

1(2(3(4(5))))

the repeated scanning leads to quadratic complexity.

Optimal Approach

The key insight is that the string already represents a preorder traversal with structural markers.

We can parse the string in a single left to right pass while maintaining the current parsing position.

Instead of repeatedly creating substrings, we:

  • Read one node value.
  • Recursively build its left subtree if the next character is (.
  • Recursively build its right subtree if another ( appears.
  • Return once the subtree is complete.

This avoids redundant scanning and processes every character exactly once.

The recursive parser naturally mirrors the recursive structure of the tree itself.

Approach Time Complexity Space Complexity Notes
Brute Force O(n²) O(n) Repeated substring creation and rescanning
Optimal O(n) O(n) Single pass recursive parsing

Algorithm Walkthrough

Optimal Recursive Parsing Algorithm

  1. Start with a global index pointing to the beginning of the string.

The index tracks our current parsing position. Since recursion processes subtrees in order, a shared index allows all recursive calls to coordinate correctly. 2. Parse the current node value.

A node value may:

  • be negative
  • contain multiple digits

First check whether the current character is '-'. Then continue reading digits until a non digit character appears. 3. Create a new tree node.

Once the integer value is parsed, create a TreeNode object for it. 4. Check whether a left subtree exists.

If the current character is '(', then the next portion of the string represents the left child.

Skip the opening parenthesis and recursively build the subtree. 5. After the recursive call finishes, skip the closing ')'.

The recursive call consumes the entire subtree content, so the current index should now point at the matching closing parenthesis. 6. Check whether a right subtree exists.

If another '(' appears immediately afterward, recursively parse the right subtree using the same logic. 7. Return the completed node.

By the time both optional subtree parses complete, the entire subtree rooted at the current node has been reconstructed.

Why it works

The algorithm works because the string format is recursively defined in exactly the same way as the tree structure itself.

Each recursive call is responsible for parsing exactly one subtree. The shared index always points to the next unprocessed character. Since every node consumes its own value and recursively consumes its children in preorder order, the parser never loses synchronization with the string structure.

Every opening parenthesis corresponds to entering a subtree, and every closing parenthesis corresponds to returning from that subtree.

Python Solution

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

from typing import Optional

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

        index = 0

        def build_tree() -> Optional[TreeNode]:
            nonlocal index

            # Parse sign
            sign = 1
            if s[index] == '-':
                sign = -1
                index += 1

            # Parse number
            value = 0
            while index < len(s) and s[index].isdigit():
                value = value * 10 + int(s[index])
                index += 1

            node = TreeNode(sign * value)

            # Parse left child
            if index < len(s) and s[index] == '(':
                index += 1  # skip '('
                node.left = build_tree()
                index += 1  # skip ')'

            # Parse right child
            if index < len(s) and s[index] == '(':
                index += 1  # skip '('
                node.right = build_tree()
                index += 1  # skip ')'

            return node

        return build_tree()

The implementation closely follows the recursive parsing algorithm.

The index variable is shared across all recursive calls using nonlocal. This avoids passing substrings around and allows the parser to process the string in a single pass.

The parser first handles the optional negative sign. After that, it accumulates digits into the node value using standard integer construction logic.

Once the node is created, the code checks whether the next character is '('. If it is, a subtree exists. The parser skips the opening parenthesis, recursively constructs the subtree, then skips the matching closing parenthesis.

The same logic is repeated for the right child.

Because the recursion consumes the string in preorder traversal order, the tree is reconstructed correctly without additional data structures.

Go Solution

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func str2tree(s string) *TreeNode {
    if len(s) == 0 {
        return nil
    }

    index := 0

    var buildTree func() *TreeNode

    buildTree = func() *TreeNode {
        sign := 1

        // Parse sign
        if s[index] == '-' {
            sign = -1
            index++
        }

        // Parse number
        value := 0
        for index < len(s) && s[index] >= '0' && s[index] <= '9' {
            value = value*10 + int(s[index]-'0')
            index++
        }

        node := &TreeNode{
            Val: sign * value,
        }

        // Parse left child
        if index < len(s) && s[index] == '(' {
            index++ // skip '('
            node.Left = buildTree()
            index++ // skip ')'
        }

        // Parse right child
        if index < len(s) && s[index] == '(' {
            index++ // skip '('
            node.Right = buildTree()
            index++ // skip ')'
        }

        return node
    }

    return buildTree()
}

The Go implementation follows the same parsing strategy as the Python version.

One notable difference is that Go does not support nested functions with nonlocal variables in the same way Python does. Instead, the recursive closure captures the index variable from the surrounding scope.

Go also uses explicit character comparisons:

s[index] >= '0' && s[index] <= '9'

instead of Python's .isdigit() helper.

The tree nodes are allocated using pointers with:

&TreeNode{}

and empty trees are represented using nil.

Worked Examples

Example 1

Input:

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

Step by Step Trace

Step Index Parsed Value Action Stack Context
1 0 4 Create root 4
2 2 2 Create left child of 4 4 -> 2
3 4 3 Create left child of 2 4 -> 2 -> 3
4 6 - Finish node 3 Return to 2
5 8 1 Create right child of 2 4 -> 2 -> 1
6 10 - Finish node 1 Return to 2
7 11 - Finish node 2 Return to 4
8 13 6 Create right child of 4 4 -> 6
9 15 5 Create left child of 6 4 -> 6 -> 5
10 17 - Finish node 5 Return to 6
11 18 - Finish node 6 Return to 4

Final tree:

        4
      /   \
     2     6
    / \   /
   3   1 5

Example 2

Input:

"4(2(3)(1))(6(5)(7))"

The process is identical to Example 1, except node 6 now has both children.

Constructed tree:

        4
      /   \
     2     6
    / \   / \
   3   1 5   7

Example 3

Input:

"-4(2(3)(1))(6(5)(7))"

Parsing the Root

Character Action
- Set sign to negative
4 Parse numeric value
Result Root value becomes -4

The remaining parsing logic is unchanged.

Final tree:

        -4
       /  \
      2    6
     / \  / \
    3  1 5  7

Complexity Analysis

Measure Complexity Explanation
Time O(n) Every character is processed once
Space O(n) Recursive call stack in worst case

The algorithm performs a single left to right traversal of the string. Each character is consumed exactly once while parsing numbers or parentheses.

The space complexity comes from recursion depth. In the worst case, the tree is completely skewed, causing recursion depth to become O(n).

Test Cases

# Helper functions for testing

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

def level_order(root):
    if not root:
        return []

    result = []
    queue = [root]

    while queue:
        node = queue.pop(0)

        if node:
            result.append(node.val)
            queue.append(node.left)
            queue.append(node.right)

    return result

# Solution instance
solution = Solution()

# Example 1
root = solution.str2tree("4(2(3)(1))(6(5))")
assert level_order(root) == [4, 2, 6, 3, 1, 5]  # standard mixed tree

# Example 2
root = solution.str2tree("4(2(3)(1))(6(5)(7))")
assert level_order(root) == [4, 2, 6, 3, 1, 5, 7]  # complete binary structure

# Example 3
root = solution.str2tree("-4(2(3)(1))(6(5)(7))")
assert level_order(root) == [-4, 2, 6, 3, 1, 5, 7]  # negative root value

# Empty input
root = solution.str2tree("")
assert root is None  # empty tree

# Single node
root = solution.str2tree("42")
assert level_order(root) == [42]  # tree with only root

# Negative single node
root = solution.str2tree("-15")
assert level_order(root) == [-15]  # negative standalone node

# Left skewed tree
root = solution.str2tree("1(2(3(4)))")
assert level_order(root) == [1, 2, 3, 4]  # deep recursion on left side

# Tree with only left child
root = solution.str2tree("1(2)")
assert level_order(root) == [1, 2]  # single left subtree

# Multi digit values
root = solution.str2tree("123(45)(678)")
assert level_order(root) == [123, 45, 678]  # multiple digit parsing
Test Why
"4(2(3)(1))(6(5))" Standard example with mixed structure
"4(2(3)(1))(6(5)(7))" Tree with both left and right children
"-4(2(3)(1))(6(5)(7))" Validates negative number parsing
"" Validates empty input handling
"42" Single node tree
"-15" Negative standalone root
"1(2(3(4)))" Deep recursion and skewed tree
"1(2)" Node with only left child
"123(45)(678)" Multi digit integer parsing

Edge Cases

Empty String

An empty string represents an empty tree. This is easy to mishandle because recursive parsing assumes at least one character exists.

The implementation handles this immediately with:

if not s:
    return None

This prevents invalid index access before parsing begins.

Negative Numbers

The string may begin with '-', and child nodes may also contain negative values.

A parser that assumes only digits will incorrectly construct values or crash when encountering '-'.

The implementation explicitly checks for the negative sign before parsing digits:

if s[index] == '-':
    sign = -1

The final value becomes:

sign * value

which correctly handles both positive and negative integers.

Deeply Nested Trees

A highly skewed tree such as:

"1(2(3(4(5))))"

creates deep recursion.

Naive substring based approaches become very inefficient because they repeatedly scan overlapping sections of the string.

The optimal solution avoids this by using a single shared index and processing each character once. Even in deeply nested trees, the total work remains linear.

Multi Digit Values

Values like "123" or "6789" require reading multiple consecutive digits.

A buggy implementation may accidentally treat each digit as a separate node.

The solution correctly accumulates digits using:

value = value * 10 + int(s[index])

which reconstructs the entire integer before creating the node.