# 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:

- 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. - If the current node is not empty, it adds the node's value to the string within parentheses.
- 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. - 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. - 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:

- Converts the value of the root node to a string and initializes the
`ans`

string. - 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. - Calls the
`buildString`

function for the right child of the root, with the`mandatory`

flag set to`false`

. - Returns the constructed string
`ans`

representing the binary tree.