How to Construct String from Binary Tree?

Given a binary tree, convert it to a string that consist of parenthesis and interests in the pre-order traversal. The empty brackets () for left sub trees can be omitted unless there is a right binary sub tree. The right empty brackets () can be omitted.

You need to construct a string consists of parenthesis and integers from a binary tree with the preorder traversing way.

The null node needs to be represented by empty parenthesis pair “()”. And you need to omit all the empty parenthesis pairs that don’t affect the one-to-one mapping relationship between the string and the original binary tree.

Example 1:

Input: Binary tree: [1,2,3,4]
       1
     /   \
    2     3
   /    
  4     

Output: “1(2(4))(3)”

Explanation: Originallay it needs to be “1(2(4)())(3()())”,
but you need to omit all the unnecessary empty parenthesis pairs.
And it will be “1(2(4))(3)”.
Example 2:

Input: Binary tree: [1,2,3,null,4]
       1
     /   \
    2     3
     \  
      4 

Output: “1(2()(4))(3)”

Explanation: Almost the same as the first example,
except we can’t omit the first parenthesis pair to break the one-to-one mapping relationship between the input and the output.

Like most of other tree problems, the puzzle can be solved by using recursion. The string representation of a empty TreeNode is also empty i.e. “”.

/**
 * 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:
    string tree2str(TreeNode* t) {
        if (t == NULL) {
            return "";
        }
        auto left = tree2str(t->left);
        auto right = tree2str(t->right);
        auto result =  std::to_string(t->val);
        // the empty brackets cannot be omitted if right tree is not NULL
        if ((right.size() > 0) || (left.size() > 0)) {
            result += "(" + left + ")";
        }
        if (right.size() > 0) {
            result += "(" + right + ")";
        }
        return result;        
    }
};

The string value is constructed bottom up following the recursive DFS (Depth First Search). If the right node is not empty, we cannot omit the left node representation if it is empty. Each node is visited exactly once so the runtime complexity is O(N) while the space complexity is O(log N) by average if it is a balanced binary tree, or O(N) if the binary tree is degraded into a linked list.

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) —