LeetCode: 606. Construct String from Binary Tree

The Problem

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

Input:  [1,2,3,null,4]
Output: "1(2()(4))(3)"

Solution

We opted for a recursive approach to tackle this problem, and upon evaluating our solution on the LeetCode platform, we achieved the following outcome:

Here's the code that led us to this result.

string tree2str(TreeNode* root) {
    string ans = to_string(root->val);
    buildString(root->left, ans, root->right != nullptr);
    buildString(root->right, ans, false);
    return ans;
}

void buildString(TreeNode *root, string &str, bool mandatory ) {

    if (root == nullptr) {
	    if (mandatory) str += "()";
    	return;
    }

    str += "(" + to_string(root->val);
    buildString(root->left, str, root->right != nullptr);
    buildString(root->right, str, false);
    str += ")";
}

    

Explanation:

The code consists of two functions:

buildString Function:

This function constructs a string representation of a binary tree by traversing through the tree recursively. It takes three arguments:

• root: A pointer to the current node being processed.
• str: A reference to the string being constructed, representing the tree.
• mandatory: A boolean flag indicating whether the parentheses around the current node are mandatory.

Here's what the buildString function does step by step:

1. If the current node (root) is empty (nullptr), and the mandatory flag is set to true, it means that the node should be represented with parentheses even though it's missing. So, in this case, it adds "()" to the string to represent the missing child node.
2. If the current node is not empty, it adds the node's value to the string within parentheses.
3. Recursively calls the buildString function for the left child of the current node. If the right child exists (root->right != nullptr), it sets the mandatory flag to true to ensure the left child's parentheses are included even if it's empty.
4. Recursively calls the buildString function for the right child of the current node. Here, the mandatory flag is always set to false, as we only include parentheses for missing left children, not for right children.
5. Finally, after processing both children, it adds a closing parenthesis to the string.

tree2str Function:

This function serves as a starting point for generating the string representation of the entire binary tree. It takes the root of the tree as input and returns the corresponding string. The main steps include:

1. Converts the value of the root node to a string and initializes the ans string.
2. Calls the buildString function for the left child of the root. If the right child exists, it sets the mandatory flag to true to ensure parentheses around the left child.
3. Calls the buildString function for the right child of the root, with the mandatory flag set to false.
4. Returns the constructed string ans representing the binary tree.