Construct Binary Tree from String

Problem

You need to construct a binary tree from a string consisting of parenthesis and integers.

The whole input represents a binary tree. It contains an integer followed by zero, one or two pairs of parenthesis. The integer represents the root’s value and a pair of parenthesis contains a child binary tree with the same structure.

You always start to construct the left child node of the parent first if it exists.

Examples

Example 1:

1
2


Input: s = "4(2(3)(1))(6(5))"
Output: [4,2,6,3,1,5]

Example 2:

1
2


Input: s = "4(2(3)(1))(6(5)(7))"
Output: [4,2,6,3,1,5,7]

Example 3:

1
2


Input: s = "-4(2(3)(1))(6(5)(7))"
Output: [-4,2,6,3,1,5,7]

Constraints:

0 <= s.length <= 3 * 10^4
s consists of digits, '(', ')', and '-' only.
All numbers in the tree have value at most than 230.

Solution

Method 1 – Recursive Parsing (DFS/Stack)

Intuition

The string encodes a binary tree using integers and parentheses. We can recursively parse the string, always building the left child first, then the right child, as per the problem statement. The recursion naturally matches the parenthesis structure.

Approach

Use a helper function that parses the string from a given index and returns the constructed node and the next index to parse.
Parse the integer value for the current node.
If the next character is ‘(’, recursively parse the left child.
If another ‘(’ follows, recursively parse the right child.
Return the constructed node and the index after the closing parenthesis.
The recursion ends when the string is fully parsed.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31


struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
class Solution {
public:
    TreeNode* str2tree(string s) {
        int i = 0;
        return parse(s, i);
    }
    TreeNode* parse(const string& s, int& i) {
        if (i >= s.size()) return nullptr;
        int sign = 1, num = 0;
        if (s[i] == '-') { sign = -1; ++i; }
        while (i < s.size() && isdigit(s[i])) num = num * 10 + (s[i++] - '0');
        TreeNode* node = new TreeNode(sign * num);
        if (i < s.size() && s[i] == '(') {
            ++i;
            node->left = parse(s, i);
            ++i;
        }
        if (i < s.size() && s[i] == '(') {
            ++i;
            node->right = parse(s, i);
            ++i;
        }
        return node;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30


type TreeNode struct {
    Val int
    Left *TreeNode
    Right *TreeNode
}
func Str2tree(s string) *TreeNode {
    var parse func(*int) *TreeNode
    parse = func(i *int) *TreeNode {
        if *i >= len(s) { return nil }
        sign, num := 1, 0
        if s[*i] == '-' { sign = -1; *i++ }
        for *i < len(s) && s[*i] >= '0' && s[*i] <= '9' {
            num = num*10 + int(s[*i]-'0'); *i++
        }
        node := &TreeNode{Val: sign*num}
        if *i < len(s) && s[*i] == '(' {
            *i++
            node.Left = parse(i)
            *i++
        }
        if *i < len(s) && s[*i] == '(' {
            *i++
            node.Right = parse(i)
            *i++
        }
        return node
    }
    i := 0
    return parse(&i)
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30


class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int x) { val = x; }
}
class Solution {
    public TreeNode str2tree(String s) {
        int[] i = {0};
        return parse(s, i);
    }
    private TreeNode parse(String s, int[] i) {
        if (i[0] >= s.length()) return null;
        int sign = 1, num = 0;
        if (s.charAt(i[0]) == '-') { sign = -1; i[0]++; }
        while (i[0] < s.length() && Character.isDigit(s.charAt(i[0])))
            num = num * 10 + (s.charAt(i[0]++) - '0');
        TreeNode node = new TreeNode(sign * num);
        if (i[0] < s.length() && s.charAt(i[0]) == '(') {
            i[0]++;
            node.left = parse(s, i);
            i[0]++;
        }
        if (i[0] < s.length() && s.charAt(i[0]) == '(') {
            i[0]++;
            node.right = parse(s, i);
            i[0]++;
        }
        return node;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25


data class TreeNode(var `val`: Int, var left: TreeNode? = null, var right: TreeNode? = null)
class Solution {
    fun str2tree(s: String): TreeNode? {
        var i = 0
        fun parse(): TreeNode? {
            if (i >= s.length) return null
            var sign = 1; var num = 0
            if (s[i] == '-') { sign = -1; i++ }
            while (i < s.length && s[i].isDigit()) num = num * 10 + (s[i++] - '0')
            val node = TreeNode(sign * num)
            if (i < s.length && s[i] == '(') {
                i++
                node.left = parse()
                i++
            }
            if (i < s.length && s[i] == '(') {
                i++
                node.right = parse()
                i++
            }
            return node
        }
        return parse()
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19


class TreeNode:
    def __init__(self, val: int, left: 'TreeNode' = None, right: 'TreeNode' = None):
        self.val = val
        self.left = left
        self.right = right
class Solution:
    def str2tree(self, s: str) -> 'TreeNode | None':
        def parse(i: int) -> tuple['TreeNode | None', int]:
            if i >= len(s): return None, i
            sign, num = 1, 0
            if s[i] == '-': sign, i = -1, i+1
            while i < len(s) and s[i].isdigit():
                num = num * 10 + int(s[i]); i += 1
            node = TreeNode(sign * num)
            if i < len(s) and s[i] == '(': left, i = parse(i+1); node.left = left; i += 1
            if i < len(s) and s[i] == '(': right, i = parse(i+1); node.right = right; i += 1
            return node, i
        node, _ = parse(0)
        return node

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39


pub struct TreeNode {
    pub val: i32,
    pub left: Option<Box<TreeNode>>,
    pub right: Option<Box<TreeNode>>,
}
impl TreeNode {
    pub fn new(val: i32) -> Self {
        TreeNode { val, left: None, right: None }
    }
}
impl Solution {
    pub fn str2tree(s: String) -> Option<Box<TreeNode>> {
        fn parse(s: &[u8], i: &mut usize) -> Option<Box<TreeNode>> {
            if *i >= s.len() { return None; }
            let mut sign = 1;
            if s[*i] == b'-' { sign = -1; *i += 1; }
            let mut num = 0;
            while *i < s.len() && s[*i].is_ascii_digit() {
                num = num * 10 + (s[*i] - b'0') as i32;
                *i += 1;
            }
            let mut node = Box::new(TreeNode::new(sign * num));
            if *i < s.len() && s[*i] == b'(' {
                *i += 1;
                node.left = parse(s, i);
                *i += 1;
            }
            if *i < s.len() && s[*i] == b'(' {
                *i += 1;
                node.right = parse(s, i);
                *i += 1;
            }
            Some(node)
        }
        let s = s.as_bytes();
        let mut i = 0;
        parse(s, &mut i)
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26


class TreeNode {
    val: number;
    left: TreeNode | null;
    right: TreeNode | null;
    constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
        this.val = val ?? 0;
        this.left = left ?? null;
        this.right = right ?? null;
    }
}
class Solution {
    str2tree(s: string): TreeNode | null {
        let i = 0;
        function parse(): TreeNode | null {
            if (i >= s.length) return null;
            let sign = 1, num = 0;
            if (s[i] === '-') { sign = -1; i++; }
            while (i < s.length && s[i] >= '0' && s[i] <= '9') num = num * 10 + +(s[i++]);
            const node = new TreeNode(sign * num);
            if (i < s.length && s[i] === '(') { i++; node.left = parse(); i++; }
            if (i < s.length && s[i] === '(') { i++; node.right = parse(); i++; }
            return node;
        }
        return parse();
    }
}

Complexity

⏰ Time complexity: O(n), where n is the length of the string. Each character is processed once.
🧺 Space complexity: O(h), where h is the height of the tree (recursion stack).

Problem#

Examples#

Solution#

Method 1 – Recursive Parsing (DFS/Stack)#

Intuition#

Approach#

Code#

Complexity#