Construct a Binary Tree from a String with Bracket Representation

Contents

ProblemExamplesVisualizationSolutionAlgorithmCode

Problem Statement❯

You are given a string that represents a binary tree using bracket notation. Your task is to construct the binary tree from this string. The format of the string is as follows: - A node is represented by its value followed optionally by its left and right subtrees in parentheses. - For example, the string '4(2(3)(1))(6(5))' represents the following tree: 4 / \ 2 6 / \ / 3 1 5 Write a function to construct the binary tree from such a string. If the string is empty, return null.

Examples❯

Input Tree Level Order Output Description
"4(2(3)(1))(6(5))"
[[4], [2, 6], [3, 1, 5]] Standard binary tree with both left and right subtrees containing nested children
"1(2)(3)"
[[1], [2, 3]] Simple binary tree with one left and one right child
"1(2(3(4)))"
[[1], [2], [3], [4]] Tree skewed to the left only, with nested left children
"1()(2()(3))"
[[1], [2], [3]] Tree skewed to the right only using empty parentheses for null children
"7"
[[7]] Single-node tree with only root
[] Empty string input results in an empty tree

Visualization Player

Solution❯

Case 1: Full Tree Structure (e.g., 4(2(3)(1))(6(5)))

In this case, the input string represents a binary tree with both left and right subtrees. We begin at the root value, which is the number before the first opening bracket. The left subtree is enclosed in the first set of parentheses and the right subtree is enclosed in the second. This representation is ideal for recursive processing — we process the root, then recursively build the left and right children.

Case 2: Only Left Subtree (e.g., 1(2))

Here, we have a root node with only a left child. This means after parsing the root (1), we encounter one set of parentheses containing the value 2. There is no second set of parentheses, so the right child is assumed to be null.

Case 3: Only Right Subtree (e.g., 1()(3))

This string has a root node with a missing left child (denoted by empty parentheses) and a right child. We create the root node (1), detect an empty set of parentheses for the left child (so it remains null), and then construct the right child (3) from the next parentheses set.

Case 4: Single Node Tree (e.g., 1)

The string contains only a single numeric value with no parentheses. This represents a tree with just one node — the root. There are no children to process, so both left and right remain null.

Case 5: Empty Input (e.g., "")

If the input string is empty, there is no tree to build. The function should simply return null in this case. This acts as a base case or edge condition in recursive implementations.

Algorithm Steps❯

  1. Given a string representing a binary tree in bracket notation (e.g., 4(2(3)(1))(6(5))).
  2. Initialize an index pointer at the start of the string.
  3. Parse the numeric value (and sign, if negative) from the current index.
  4. Create a new tree node with the parsed value.
  5. If the next character is (, recursively construct the left subtree and skip the corresponding ).
  6. If another ( follows, recursively construct the right subtree and skip its closing ).
  7. Return the constructed node and update the index.
  8. Repeat the process until the entire string is parsed and the binary tree is built.

Code

Python
Java
JavaScript
C
C++
C#
Kotlin
Swift
Go
Php
class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

def str2tree(s: str):
    if not s:
        return None
    def helper(i):
        # Parse number (handle negative numbers)
        sign = 1
        if s[i] == '-':
            sign = -1
            i += 1
        num = 0
        while i < len(s) and s[i].isdigit():
            num = num * 10 + int(s[i])
            i += 1
        node = TreeNode(sign * num)
        # Parse left subtree if '(' found
        if i < len(s) and s[i] == '(':
            i += 1  # skip '('
            node.left, i = helper(i)
            i += 1  # skip ')'
        # Parse right subtree if '(' found
        if i < len(s) and s[i] == '(':
            i += 1  # skip '('
            node.right, i = helper(i)
            i += 1  # skip ')'
        return node, i
    root, _ = helper(0)
    return root

# Example usage:
if __name__ == '__main__':
    s = "4(2(3)(1))(6(5))"
    root = str2tree(s)
    # A function to print the tree can be added for verification
    print(root.val)