# Construct String from Binary Tree
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/construct-string-from-binary-tree)
Canonical: https://scaleengineer.com/dsa/problems/construct-string-from-binary-tree
**Algorithms:** [Depth-First Search](https://scaleengineer.com/algorithms/depth-first-search), [Merkle Tree](https://scaleengineer.com/algorithms/merkle-tree)
**Data structures:** String, Tree, Binary Tree
---
## Problem
Given the `root` node of a binary tree, your task is to create a string representation of the tree following a specific set of formatting rules. The representation should be based on a preorder traversal of the binary tree and must adhere to the following guidelines:

* **Node Representation**: Each node in the tree should be represented by its integer value.
* **Parentheses for Children**: If a node has at least one child (either left or right), its children should be represented inside parentheses. Specifically:

  * If a node has a left child, the value of the left child should be enclosed in parentheses immediately following the node's value.
  * If a node has a right child, the value of the right child should also be enclosed in parentheses. The parentheses for the right child should follow those of the left child.
* **Omitting Empty Parentheses**: Any empty parentheses pairs (i.e., `()`) should be omitted from the final string representation of the tree, with one specific exception: when a node has a right child but no left child. In such cases, you must include an empty pair of parentheses to indicate the absence of the left child. This ensures that the one-to-one mapping between the string representation and the original binary tree structure is maintained.  
In summary, empty parentheses pairs should be omitted when a node has only a left child or no children. However, when a node has a right child but no left child, an empty pair of parentheses must precede the representation of the right child to reflect the tree's structure accurately.

**Example 1:**

![](https://assets.glich.co/dsa/construct-string-from-binary-tree/image0.jpg) 

**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 empty parenthesis pairs. And it will be "1(2(4))(3)".

**Example 2:**

![](https://assets.glich.co/dsa/construct-string-from-binary-tree/image1.jpg) 

**Input:** root = [1,2,3,null,4]
**Output:** "1(2()(4))(3)"
**Explanation:** Almost the same as the first example, except the `()` after `2` is necessary to indicate the absence of a left child for `2` and the presence of a right child.

**Constraints:**

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

# Approaches
## Recursive Approach with String Concatenation
This approach uses a straightforward recursive method that mirrors the preorder traversal structure required by the problem. For each node, it recursively generates the string for its left and right subtrees and then concatenates them with the node's value and the necessary parentheses according to the specified rules.
**Time:** O(N^2) in the worst case (a skewed tree), where N is the number of nodes. This is because string concatenation takes time proportional to the string lengths, and in a skewed tree, intermediate strings can grow up to O(N) in length. · **Space:** O(N^2) in the worst case. The recursion depth can be up to O(N) for a skewed tree, and at each level of recursion, new strings are created. The total space for these intermediate strings can be quadratic.
**Pros:** Simple to understand and implement.; The code directly follows the problem's recursive definition, making it very intuitive.
**Cons:** Highly inefficient for large or skewed trees due to the nature of string concatenation in Java, which creates a new string object for each operation.; Can lead to `O(N^2)` time and space complexity in the worst-case scenario, potentially causing performance issues or memory limits to be exceeded.
### Explanation
The core of this method is a recursive function that processes the tree in a preorder fashion. The function's logic directly maps to the problem's requirements.

- The base case for the recursion is when the node is `null`, in which case it returns an empty string.
- For a non-null node, it first converts the node's value to a string.
- It then makes recursive calls for the left and right children to get their string representations.
- Based on whether the left and right subtree strings are empty, it applies the formatting rules:
  - If both children are null (resulting in empty strings), it returns just the node's value.
  - If the right child is null, it appends the left subtree's string enclosed in parentheses.
  - If the right child is not null, it appends both the left and right subtrees' strings, each enclosed in parentheses. The required `()` for a null left child with a non-null right child is handled naturally because the recursive call for the null left child returns an empty string, which is then wrapped in parentheses.

The main drawback is the use of `+` for string concatenation in a loop or recursion, which is inefficient in Java as it creates new `String` objects repeatedly.

```java
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public String tree2str(TreeNode root) {
        if (root == null) {
            return "";
        }

        String s = Integer.toString(root.val);

        String leftStr = tree2str(root.left);
        String rightStr = tree2str(root.right);

        if (leftStr.isEmpty() && rightStr.isEmpty()) {
            return s;
        }

        if (rightStr.isEmpty()) {
            return s + "(" + leftStr + ")";
        }

        return s + "(" + leftStr + ")(" + rightStr + ")";
    }
}
```
### Algorithm
- The base case for the recursion is a `null` node, for which an empty string is returned.
- For a non-null node, convert its value to a string `s`.
- Recursively compute the string representation for the left (`leftStr`) and right (`rightStr`) subtrees.
- Combine the results based on the rules:
  - If both `leftStr` and `rightStr` are empty, it means the node is a leaf. Return just `s`.
  - If `rightStr` is empty (but `leftStr` is not), it means there's only a left child. Return `s + "(" + leftStr + ")"`.
  - If `rightStr` is not empty, it means there's a right child. In this case, the left child's representation must be included, even if it's empty. Return `s + "(" + leftStr + ")(" + rightStr + ")"`.

## Optimized Recursive Approach with StringBuilder
This approach refines the first one by replacing inefficient string concatenation with a `StringBuilder`. A `StringBuilder` is mutable, allowing for efficient appending of characters and strings. This optimization brings the time complexity down to linear, as each node and parenthesis is appended only once.
**Time:** O(N), where N is the number of nodes. Each node is visited exactly once, and `StringBuilder.append()` operations take amortized O(1) time. · **Space:** O(N), where N is the number of nodes. The recursion depth can go up to O(H) where H is the height of the tree (H can be N in a skewed tree). The `StringBuilder` also requires O(N) space to build the final string.
**Pros:** Highly efficient with a linear time complexity, making it suitable for large trees.; Optimal space usage for this problem.; Avoids the overhead of creating many temporary string objects.
**Cons:** Slightly more complex than the direct string concatenation approach due to the need to pass a `StringBuilder` object through the recursive calls.
### Explanation
The logic remains a preorder traversal, but the implementation is optimized for performance. Instead of returning new strings at each recursive step, we pass a single `StringBuilder` instance down the call stack and append to it.

- A helper function `preorder(node, sb)` is defined to build the string representation for the subtree rooted at `node` into the `StringBuilder sb`.
- The base case is a `null` node, where the function simply returns.
- For a non-null node, it first appends the node's value.
- It then conditionally processes the children:
  - **Left Child**: If the left child exists, we append an opening parenthesis `(`, make a recursive call for the left subtree, and then append a closing parenthesis `)`.
  - **Right Child**: If the right child exists, we must handle two sub-cases. First, if the left child is `null`, we must append an empty pair of parentheses `()` to signify the absent left child. After that (or if the left child was not null), we append `(`, make the recursive call for the right subtree, and append `)`.

This method avoids creating numerous intermediate strings, leading to an optimal solution.

```java
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public String tree2str(TreeNode root) {
        if (root == null) {
            return "";
        }
        StringBuilder sb = new StringBuilder();
        preorder(root, sb);
        return sb.toString();
    }

    private void preorder(TreeNode t, StringBuilder sb) {
        sb.append(t.val);

        if (t.left != null) {
            sb.append("(");
            preorder(t.left, sb);
            sb.append(")");
        }

        if (t.right != null) {
            if (t.left == null) {
                sb.append("()");
            }
            sb.append("(");
            preorder(t.right, sb);
            sb.append(")");
        }
    }
}
```
### Algorithm
- The main `tree2str` function handles the `null` root case and initializes a `StringBuilder`.
- A recursive helper function, `preorder(node, sb)`, is used to perform the traversal and build the string.
- In `preorder`, if the current node is `null`, it returns.
- It appends the current node's value to the `StringBuilder`.
- It checks for the existence of left and right children to decide on parentheses:
  - If the left child is not `null`, append `(`, recursively call `preorder` for the left child, and then append `)`.
  - If the right child is not `null`, first check if the left child is `null`. If it is, append the mandatory `()` for the empty left child. Then, append `(`, recursively call `preorder` for the right child, and append `)`.

# Solutions
### Java

```java
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { public String tree2str ( TreeNode root ) { if ( root == null ) { return "" ; } if ( root . left == null && root . right == null ) { return root . val + "" ; } if ( root . right == null ) { return root . val + "(" + tree2str ( root . left ) + ")" ; } return root . val + "(" + tree2str ( root . left ) + ")(" + tree2str ( root . right ) + ")" ; } }
```

### CPP

```cpp
/** * Definition for a binary tree node. * 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 ) return "" ; if ( ! root -> left && ! root -> right ) return to_string ( root -> val ); if ( ! root -> right ) return to_string ( root -> val ) + "(" + tree2str ( root -> left ) + ")" ; return to_string ( root -> val ) + "(" + tree2str ( root -> left ) + ")(" + tree2str ( root -> right ) + ")" ; } };
```

### Python

```python
# Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution : def tree2str ( self , root : Optional [ TreeNode ]) -> str : def dfs ( root ): if root is None : return '' if root . left is None and root . right is None : return str ( root . val ) if root . right is None : return f ' { root . val } ( { dfs ( root . left ) } )' return f ' { root . val } ( { dfs ( root . left ) } )( { dfs ( root . right ) } )' return dfs ( root )
```