Leetcode journey - Question 606 - Construct String from Binary Tree

Problem:

Q606. Construct String from Binary Tree

👇Jump to solution

Given the root of a binary tree, construct a string consisting of parenthesis and integers from a binary tree with the preorder traversal way, and return it.

Omit all the empty parenthesis pairs that do not affect the one-to-one mapping relationship between the string and the original binary tree.

Example 1:

Input: root = [1,2,3,4]
Output: "1(2(4))(3)"
Explanation: Originally, 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: root = [1,2,3,null,4]
Output: "1(2()(4))(3)"
Explanation: Almost the same as the first example, except we cannot omit the first parenthesis pair to break the one-to-one mapping relationship between the input and the output.

Constraints:

• The number of nodes in the tree is in the range [1, 104].
• -1000 <= Node.val <= 1000

Solution:

Approach:

After observing the question we can see that we have traverse the tree in preorder fashion for that we can use recursion.
We will create a string and we will update the string according to the condition while traversing the tree.

There are 4 cases:

1. If the left and right subtree of the current node is NULL then we will return the string with the value of the current node.
2. If the left subtree is NULL and right subtree is not NULL then we will return the string with the value of the current node then we have to add () to the string and then we will call the function recursively for the right subtree.
3. If the left subtree is not NULL and right subtree is NULL then we will return the string with the value of the current node then we will call the function recursively for the left subtree.
4. If the left subtree is not NULL and right subtree is not NULL then we will return the string with the value of the current node then we will call the function recursively for the left subtree and then we will call the function recursively for the right subtree.

And that's pretty much it. Let's look at the code now

Pseudo code:

function tree2str(root):
    if root is NULL:
        return ""
    ans = value of root
    if left subtree is NULL and right subtree is NULL:
        return ans
    if left subtree is NULL:
        return ans + "()" + "(" + tree2str(root->right) + ")"
    if right subtree is NULL:
        return ans + "(" + tree2str(root->left) + ")"
    return ans + "(" + tree2str(root->left) + ")" + "(" + tree2str(root->right) + ")"
end function

Now, we can write the code:

Code:

#include <bits/stdc++.h>
using namespace std;

struct TreeNode
{
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

class Solution
{
public:
    string tree2str(TreeNode *root)
    {
        if (root == NULL)
        {
            return "";
        }
        string ans = to_string(root->val);
        if (root->left == NULL && root->right == NULL)
        {
            return ans;
        }
        if (root->left == NULL) // that means root->right != NULL
        {
            return ans + "()" + "(" + tree2str(root->right) + ")";
        }
        if (root->right == NULL)
        {
            return ans + "(" + tree2str(root->left) + ")";
        }
        return ans + "(" + tree2str(root->left) + ")" + "(" + tree2str(root->right) + ")";
    }
};
int main()
{
    TreeNode *root = new TreeNode(1);
    // root->left = new TreeNode(2);
    // root->right = new TreeNode(3);
    // root->left->left = new TreeNode(4);
    Solution s;
    cout << s.tree2str(root) << endl;
    return 0;
}

Complexity Analysis:

Time Complexity: O(n)
Space Complexity: O(n)
Hope this helps!

• If you have any questions, please leave a comment below. 💭
  

• If you like this article, please share it with your friends. 💖
  

• If you want to read more articles like this, please follow me.
  

Thank you for reading!