Construct a Binary Tree from a String with Bracket Representation

Algorithm Steps

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

Construct a Binary Tree from a String with Bracket Representation - Code Examples Code

Python

Java

JavaScript

C++

Kotlin

Swift

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)