Leetcode 536. Construct Binary Tree from String

Problem Explanation

Given a string that represents a binary tree, you are asked to construct this binary tree and return its root node.

This binary tree string representation will follow an Integer first followed by zero to two pairs of parenthesis which will be followed by an Integer only or the same child node pattern with an Integer first followed by zero to two pairs of parenthesis (i.e. each parenthesis pair represent a child node or subtree).

Example

Let's take an example to explain this :

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

This string represents the following binary tree.

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

Solution Approach

To solve this problem, recursive method can be used where an Integer (root value) is found, both left and right children are then found by recursively calling for next values until a parenthesis is found because it indicates either the end of children of a root or start of a right child.

Python Solution

1
2python
3class TreeNode:
4    def __init__(self, x):
5        self.val = x
6        self.left = None
7        self.right = None
8
9class Solution:
10    def str2tree(self, s):
11        def t(val, children):
12            node = TreeNode(int(val))
13            if children:
14                node.left = children[0]
15                if len(children) > 1:
16                    node.right = children[1]
17            return node
18        return eval('t' + s) if s else None

Here we can recursively construct a left child first and then a right child.

Java Solution

1
2java
3public class TreeNode {
4    int val;
5    TreeNode left;
6    TreeNode right;
7    TreeNode(int x) { val = x; }
8}
9
10public class Solution {
11    public TreeNode str2tree(String s) {
12        if (s == null || s.length() == 0) return null;
13        int firstParen = s.indexOf("(");
14        int val = firstParen == -1 ? Integer.parseInt(s) : Integer.parseInt(s.substring(0, firstParen));
15        TreeNode cur = new TreeNode(val);
16        if (firstParen == -1) return cur;
17        int start = firstParen, leftParenCount = 0;
18        for (int i=start;i<s.length();i++) {
19            if (s.charAt(i) == '(') leftParenCount++;
20            else if (s.charAt(i) == ')') leftParenCount--;
21            if (leftParenCount == 0 && start == firstParen) {
22                cur.left = str2tree(s.substring(start+1,i)); 
23                start = i+1;
24            } else if (leftParenCount == 0) cur.right = str2tree(s.substring(start+1,i));
25        }
26        return cur;
27    }
28}

This Java solution works by recursively trying to break down the string into sub trees, and creating new Tree nodes as we go along.

JavaScript Solution

1
2javascript
3var str2tree = function(s) {
4    if (!s) {
5        return null;
6    }
7    let i = 0;
8    while ((s[i] >= '0' && s[i] <= '9') || s[i] == '-') {
9        i++;
10    }
11    const num = Number(s.slice(0, i));
12    let left = null;
13    let right = null;
14    const node = new TreeNode(num);
15    if (s[i] == '(') {
16        let step = 0
17        for (let j = i + 1; j < s.length; j++) {
18            if (s[j] == '(') {
19                step++;
20            }
21            if (s[j] == ')') {
22                step--;
23            }
24            if (step == 0) {
25                node.left = str2tree(s.slice(i + 1, j));
26                i = j + 2;
27                break;
28            }
29        }
30    }
31    if (s[i] == '(') {
32        let step = 0
33        for (let j = i + 1; j < s.length; j++) {
34            if (s[j] == '(') {
35                step++;
36            }
37            if (s[j] == ')') {
38                step--;
39            }
40            if (step == 0) {
41                node.right = str2tree(s.slice(i + 1, j));
42                i = j + 2;
43                break;
44            }
45        }
46    } 
47    return node;
48};

Here, we just iterate through the string to split it into different parts and then recursively call the function for each of the sub string which represents a child tree.

C# Solution

1
2C#
3public class TreeNode {
4    public int val;
5    public TreeNode left;
6    public TreeNode right;
7    public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
8        this.val = val;
9        this.left = left;
10        this.right = right;
11    }
12}
13public class Solution {
14    int index = 0;
15    public TreeNode Str2tree(string s) {
16        if(string.IsNullOrEmpty(s)) return null;
17        return dfs(s);
18    }
19    TreeNode dfs(string s)
20    {
21        if(index >= s.Length) return null;
22        bool sign = false;
23        if(s[index] == '-')
24        {
25            sign = true;
26            index++;
27        }
28        int num = 0;
29        while(index < s.Length && Char.IsDigit(s[index])){
30            num = num * 10 + (s[index++] - '0');
31        }
32        num = sign ? -num : num;
33        TreeNode node = new TreeNode(num);
34        if(index < s.Length && s[index] == '(')
35        {
36            index++;
37            node.left = dfs(s);
38            index++;
39        }
40        if(index < s.Length && s[index] == '(')
41        {
42            index++;
43            node.right = dfs(s);
44            index++;
45        }
46        return node;
47    }
48}

In this C# solution, we are using a depth-first-search approach to find if parentheses '(' are present or not to know if the next value is a subtree or not.

This solution works in a similar fashion to the previous solutions but we are also accounting for the '-' case when the values of nodes are negative.

C++ Solution

1
2C++
3struct TreeNode {
4    int val;
5    TreeNode *left;
6    TreeNode *right;
7    TreeNode() : val(0), left(nullptr), right(nullptr) {}
8    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
9    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
10};
11
12class Solution {
13public:
14    TreeNode* str2tree(string s) {
15        int i = 0;
16        return myStr2tree(s, i);
17    }
18    TreeNode* myStr2tree(string& s, int& i) {
19        if(i >= s.size()) return nullptr;
20        int flag = 1;
21        if(s[i] == '-') {
22            flag = -1;
23            i++;
24        }
25        int num = 0;
26        while(i < s.size() && isdigit(s[i])) {
27            num = 10 * num + s[i] - '0';
28            i++;
29        }
30        TreeNode* newNode = new TreeNode(num * flag);
31        if(s[i] == '(') {
32            i++;
33            newNode->left = myStr2tree(s, i);
34            i++;
35        }
36        if(s[i] == '(') {
37            i++;
38            newNode->right = myStr2tree(s, i);
39            i++;
40        }
41        return newNode;
42    }
43};

In this C++ solution, myStr2tree function recursively construct a binary tree from the string where a root value is found, and its children attribute is set by the recursive call until a parenthesis is found.# Ruby Solution

1
2ruby
3class TreeNode
4	attr_accessor :val, :left, :right
5  def initialize(val = 0, left = nil, right = nil)
6    @val = val
7    @left = left
8    @right = right
9  end
10end
11
12def str2tree(s)
13  s = s.split('')
14  str2tree_helper(s)
15end
16
17def str2tree_helper(s)
18  if s.empty?
19     return nil
20  end
21end
22
23val = 0
24is_negative = false
25if s.first == "-"
26    is_negative = true
27    s.shift
28end
29
30while !s.empty? && s.first != "(" && s.first != ")"
31    val = val * 10 + s.shift.to_i
32end
33
34val = is_negative ? -val : val
35
36node = TreeNode.new(val)
37
38if s.first == "("
39    s.shift
40    node.left = str2tree_helper(s)
41    s.shift
42end
43if s.first == "("
44    s.shift
45    node.right = str2tree_helper(s)
46    s.shift
47end
48
49node

In this Ruby solution, we are using a helper function to construct the binary tree from the string representation. The helper function recursively creates a new node for every value it encounters in the string. It then checks if the next value is an open parenthesis, "(" , if it is, it calls itself recursively to create the left or right child node. This process continues until all values in the string have been parsed.

TypeScript Solution

1
2typescript
3class TreeNode {
4    val: number;
5    left: TreeNode | null;
6    right: TreeNode | null;
7    constructor(val = 0, left: TreeNode | null = null, right: TreeNode | null = null) {
8        this.val = val;
9        this.left = left;
10        this.right = right;
11    }
12}
13
14function str2tree(s: string): TreeNode | null {
15    if (!s) return null;
16    let index = s.indexOf('(');
17    let val = index != -1 ? s.slice(0, index) : s;
18    let cur = new TreeNode(parseInt(val));
19    if (index == -1) return cur;
20    let start = index, count = 0;
21    for (let i = start; i < s.length; i++) {
22        if(s.charAt(i) == '(') count++;
23        if(s.charAt(i) == ')') count--;
24        if (count == 0 && start == index) {
25            cur.left = str2tree(s.slice(start + 1, i))
26            start = i + 1;
27        }
28        else if(count == 0){
29            cur.right = str2tree(s.slice(start + 1, i));
30            break;
31        }
32    }
33    return cur;
34}

The TypeScript solution is along the same lines of the JavaScript one, with the addition of TypeScript specific syntax and types. We are parsing the string and constructing the binary tree using recursion. For each node, we find its value, and then find its children recursively.


Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫