How to Construct Binary Tree from String (Binary Tree Deserialization Algorithm)

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.

Example:
Input: “4(2(3)(1))(6(5))”
Output: return the tree root node representing the following tree:

       4
     /   \
    2     6
   / \   / 
  3   1 5   

Note:
There will only be ‘(‘, ‘)’, ‘-‘ and ‘0’ ~ ‘9’ in the input string.
An empty tree is represented by “” instead of “()”.

Binary Tree Deserialization Algorithm via Divide and Conquer using Recursion

We notice that the string is recursively in the form of X(LEFT)(RIGHT) where the (RIGHT) can be omitted if the right sub tree is null. Therefore, we need to find the separation between left and right subtree, and thus we can recursively construct the left and right sub trees.

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
40
41
42
43

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* str2tree(string s) {
        if (s.size() == 0) {
            return nullptr;
        }
        // i don't know why adding this check works..
        if (s[0] == ')') return nullptr; 
        int j = 0;
        // find characters before first opening curly brace
        while (j < s.size() && s[j] != '(') j ++; 
        TreeNode* root = new TreeNode(std::stoi(s.substr(0, j)));
        int left = 0, i = j;
        // find the separation between left and right tree
        while (i < s.size()) {
            if (s[i] == '(') {
                left ++;
            } else if (s[i] == ')') {
                left --;
            }
            if (left == 0) { // the last closing curly brace for left tree
                break;
            }
            i ++;
        }
        if (j < s.size() - 1) { // if left tree is not null
            root->left = str2tree(s.substr(j + 1, i - 1 - j));
        }
        if (i + 1 < s.size() - 1) { // if right tree is not null
            root->right = str2tree(s.substr(i + 2, s.size() - i - 2));   
        }
        return root;
    }
};

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* str2tree(string s) {
        if (s.size() == 0) {
            return nullptr;
        }
        // i don't know why adding this check works..
        if (s[0] == ')') return nullptr; 
        int j = 0;
        // find characters before first opening curly brace
        while (j < s.size() && s[j] != '(') j ++; 
        TreeNode* root = new TreeNode(std::stoi(s.substr(0, j)));
        int left = 0, i = j;
        // find the separation between left and right tree
        while (i < s.size()) {
            if (s[i] == '(') {
                left ++;
            } else if (s[i] == ')') {
                left --;
            }
            if (left == 0) { // the last closing curly brace for left tree
                break;
            }
            i ++;
        }
        if (j < s.size() - 1) { // if left tree is not null
            root->left = str2tree(s.substr(j + 1, i - 1 - j));
        }
        if (i + 1 < s.size() - 1) { // if right tree is not null
            root->right = str2tree(s.substr(i + 2, s.size() - i - 2));   
        }
        return root;
    }
};

As the numbers could be negative, we scan for the first occurrence of opening left curly brace, then we keep scanning until the matched closed curly brace, where the left tree definition ends. As the string is well-formed, then we assume the rest of the string should be the definition of the right tree.

Recursively, we call the function and construct its left and right tree respectively.

Now, the reverse process is called seralization which is easy using the DPS algorithm: How to Serialize and Deserialize Binary Tree?

Related Binary Tree Construction Algorithms

You may also like the following posts on the similar tree problems.

• Recursive Algorithm to Construct Binary Tree from Preorder and Postorder Traversal
• How to Construct Binary Search Tree from Preorder Traversal in Python?
• Algorithm to Construct Binary Tree from Preorder and Inorder Traversal
• How to Construct Binary Search Tree from Preorder Traversal? (C++ and Java)
• How to Construct String from Binary Tree?
• How to Balance a Binary Search Tree using Recursive Inorder Traversal Algorithm?
• How to Construct the Maximum Binary Tree using Divide-and-Conquer Recursion Algorithm?
• How to Construct Binary Tree from Inorder and Postorder Traversal using Depth First Search Algorithm (Recursion)?
• How to Construct Binary Tree from String (Binary Tree Deserialization Algorithm)

–EOF (The Ultimate Computing & Technology Blog) —