Leetcode 606. Construct String from Binary Tree

Problem Explanation:

You are given a binary tree where each node has a single digit integer. Your task is to construct a string using pre-order traversal of the binary tree.

No space in the string should be wasted. For any node of the binary tree, if a right child exists but the left child doesn't exist, still you have to consider it as "()". If not, you can drop leaf nodes.

Example:

For example, consider the following binary tree:

1
2
3   1
4 /   \
52     3
6 \
7  4

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

Output: "1(2()(4))(3)"

Here, 1 is the root. It has a left child 2 and a right child 3. Node 2 has only a right child 4. Node 4 is a leaf node, but we cannot drop this leaf node because it is a right child and we have to represent the absent left child by "()" giving us "(2()(4))". Same for node 3, it can be represented as "$(3)$". Combining them, we get the final answer "1(2()(4))(3)".

Approach:

The solution uses a simple Depth-First Search (DFS) based strategy.

• If the node we are at is a null node, we will return an empty string.
• If the node we are at is not null, we will convert the node value into string, and look for its children.
• If the node has a right child, it should be included in the output string whether left child exists or not. So recursively, we will get the string for the left child and the right child and attach them together.
• If the node only has a left child, then we don't need "()" for the right child. Hence, we will get the string for the left child and attach it to the root.

Solutions:

Below are the solutions in different programming languages:

Python

1
2python
3class Solution:
4    def tree2str(self, t: TreeNode) -> str:
5        if not t: 
6            return ''
7        left = '({})'.format(self.tree2str(t.left)) if (t.left or t.right) else ''
8        right = '({})'.format(self.tree2str(t.right)) if t.right else ''
9        return '{}{}{}'.format(t.val, left, right)

Java

1
2java
3public class Solution {
4    public String tree2str(TreeNode t) {
5        if (t == null) {
6            return "";
7        }
8        String result = t.val + "";
9        String left = tree2str(t.left);
10        String right = tree2str(t.right);
11        if (left == "" && right == "") {
12            return result;
13        }
14        if (left == "") {
15            return result + "()(" + right + ")";
16        }
17        if (right == "") {
18            return result + "(" + left + ")";
19        }
20        return result + "(" + left + ")(" + right + ")";
21    }
22}

JavaScript

1
2javascript
3var tree2str = function(t) {
4    if (!t) {
5        return '';
6    }
7    const left = `(${tree2str(t.left)})`;
8    const right = `(${tree2str(t.right)})`;
9    if (right === '()') {
10        return `${t.val}${t.left ? left : ''}`;
11    }
12    return `${t.val}${left}${right}`;
13};

C++

1
2cpp
3class Solution {
4public:
5    string tree2str(TreeNode* t) {
6        if (!t) return "";
7        string s = to_string(t->val);
8        if (t->left) {
9            s += "(" + tree2str(t->left) + ")";
10        } else if (t->right) {
11            s += "()";
12        }
13        if (t->right) {
14            s += "(" + tree2str(t->right) + ")";
15        }
16        return s;
17    }
18};

C#

1
2csharp
3public class Solution {
4    public string Tree2str(TreeNode t) {
5        if (t == null)
6            return "";
7        
8        string result = t.val.ToString();
9        string left = Tree2str(t.left);
10        string right = Tree2str(t.right);
11
12        if (left == "" && right == "")
13            return result;
14        
15        if (left == "")
16            return result + "()(" + right + ")";
17        
18        if (right == "")
19            return result + "(" + left + ")";
20
21        return result + "(" + left + ")(" + right + ")";
22    }
23}

After implementing the solution using these programming languages, we can see that DFS is a powerful strategy to solve tree-related problems. This problem can be approached by checking each node and deciding whether to add parentheses (and child nodes) based on the existence of right children and left children.

In Python, we have implemented a recursive function tree2str where for each node, we first check if it is null, if so, return an empty string. Then we process the left and right child nodes. If either of them exist or both exist, we put parentheses around their transformation. We use string formatting to add the parentheses and join the results together.

In Java, we first convert the node's value to a string. Then we recursively call tree2str for left and right children. Based on the condition, we add the parentheses and finally return the result.

In JavaScript, we first check if there is no node present. If so, we return an empty string. Then, similar to the Python solution, we process the left and right child nodes and return the result by formatting the strings accordingly.

The same concept is applied with C++ and C# solutions by following the same logic but with syntax and code structure that is appropriate for each specific language.

The key takeaway from this problem is that using a DFS strategy can make this problem relatively straightforward to solve. We recursively check each node and format it into a string by adding parentheses when necessary. This solution is efficient and clean, and can be easily implemented in various programming languages.