Code Implementation

# 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, t: TreeNode) -> str:
        if not t:
            return ""
        left = self.tree2str(t.left)
        right = self.tree2str(t.right)
        if not t.left and not t.right:
            return str(t.val)
        if not t.right:
            return f"{t.val}({left})"
        return f"{t.val}({left})({right})"
      

// Definition for a binary tree node.
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution {
public:
    string tree2str(TreeNode* t) {
        if (!t) return "";
        string left = tree2str(t->left);
        string right = tree2str(t->right);
        if (!t->left && !t->right)
            return to_string(t->val);
        if (!t->right)
            return to_string(t->val) + "(" + left + ")";
        return to_string(t->val) + "(" + left + ")(" + right + ")";
    }
};
      

// Definition for a binary tree node.
public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

class Solution {
    public String tree2str(TreeNode t) {
        if (t == null) return "";
        String left = tree2str(t.left);
        String right = tree2str(t.right);
        if (t.left == null && t.right == null)
            return String.valueOf(t.val);
        if (t.right == null)
            return t.val + "(" + left + ")";
        return t.val + "(" + left + ")(" + right + ")";
    }
}
      

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} t
 * @return {string}
 */
var tree2str = function(t) {
    if (!t) return "";
    let left = tree2str(t.left);
    let right = tree2str(t.right);
    if (!t.left && !t.right) return t.val.toString();
    if (!t.right) return t.val + "(" + left + ")";
    return t.val + "(" + left + ")(" + right + ")";
};
      

Problem Description

• Each node's value is represented as a string.
• If a node has a left child, enclose the left subtree's string in parentheses () immediately after the node's value.
• If a node has a right child, enclose the right subtree's string in parentheses () immediately after the left subtree string.
• If a node has only a right child, you must include empty parentheses () to indicate the missing left child.
• Omit all unnecessary empty parenthesis pairs that do not affect the one-to-one mapping between the string and the original tree.

You are guaranteed that there is only one valid string for each tree, and you should not reuse any elements from the input tree.

Thought Process

• Should you add parentheses for the left and/or right child?
• Should you omit them to keep the string minimal but still unambiguous?

Solution Approach

1. Base Case: If the current node is null, return an empty string.
2. Leaf Node: If both left and right children are null, return the node's value as a string.
3. Only Left Child: If there is only a left child, return the node's value followed by the left subtree in parentheses.
4. Only Right Child: If there is only a right child, include empty parentheses for the missing left child, then include the right subtree in parentheses.
5. Both Children: If both children exist, include both subtrees in their respective parentheses.

This approach ensures that the output string is minimal yet uniquely maps back to the original tree structure. Recursion is used because each subtree can be represented in the same way as the whole tree.

Example Walkthrough

Consider the following binary tree:

        1
       / \
      2   3
       \
        4
  

• Start at node 1. It has both left and right children.
• For the left child (2):
  • Node 2 has no left child, but has a right child (4).
  • We must include empty parentheses for the missing left child: 2()(...).
  • Process node 4: it's a leaf, so just "4".
  • So, left subtree is 2()(4).
• For the right child (3): it's a leaf, so just "3".
• Combine: 1(2()(4))(3)

This string uniquely and minimally represents the tree structure.

Time and Space Complexity

• Brute-force approach: If you tried to generate all possible strings and then check which one matches the tree, the time complexity would be exponential, as you'd be exploring all possible string combinations for each subtree.
• Optimized (recursive) approach: Each node is visited exactly once, and at each node, you perform a constant amount of work (constructing strings and concatenating). Thus, the time complexity is O(N), where N is the number of nodes in the tree.
• The space complexity is also O(N) due to the recursion stack and the space required to build the output string.

Summary