606. Construct String From Binary Tree - Explanation

Problem Link

1. Depth First Search

Intuition

We need to create a string representation using preorder traversal with parentheses. The key observation is handling empty subtrees: we must include empty parentheses () for a missing left child only when a right child exists (to preserve the tree structure), but we can omit parentheses for a missing right child entirely.

Algorithm

1. If the node is null, return an empty string.
2. Recursively get string representations of left and right subtrees.
3. If both children exist, return "val(left)(right)".
4. If only the right child exists, return "val()(right)" (empty parentheses for missing left).
5. If only the left child exists, return "val(left)" (no parentheses needed for missing right).
6. If the node is a leaf, return just its value as a string.

# 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:
        if not root:
            return ""

        cur = root.val
        left = self.tree2str(root.left)
        right = self.tree2str(root.right)

        if left and right:
            return f"{cur}({left})({right})"

        if right:
            return f"{cur}()({right})"

        if left:
            return f"{cur}({left})"

        return str(cur)

Time & Space Complexity

• Time complexity: $O(n ^ 2)$
• Space complexity: $O(n)$

---

2. Depth First Search (Optimal)

Intuition

The previous approach creates many intermediate strings during concatenation, which is inefficient. Instead, we can use a StringBuilder (or list) to accumulate characters. We always add an opening parenthesis before processing a node and a closing parenthesis after, then trim the outermost parentheses at the end.

Algorithm

1. Create a result list or StringBuilder.
2. Define a preorder function that:
   • Returns immediately if the node is null.
   • Appends "(" followed by the node's value.
   • If left is null but right exists, appends "()".
   • Recursively processes left, then right.
   • Appends ")".
3. Call preorder on the root.
4. Join the result and remove the first and last characters (the extra outer parentheses).

# 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:
        res = []

        def preorder(root):
            if not root:
                return
            res.append("(")
            res.append(str(root.val))
            if not root.left and root.right:
                res.append("()")
            preorder(root.left)
            preorder(root.right)
            res.append(")")

        preorder(root)
        return "".join(res)[1:-1]

Time & Space Complexity

• Time complexity: $O(n)$
• Space complexity: $O(n)$

---

3. Iterative DFS

Intuition

We can convert the recursive approach to iterative using an explicit stack. The challenge is knowing when we have finished processing a node's subtrees so we can add the closing parenthesis. We track the last visited node to determine whether we are returning from the right subtree.

Algorithm

1. Use a stack for traversal and track the last visited node.
2. While current node exists or stack is not empty:
   • If current exists, append "(val", handle missing left child if right exists, push to stack, move to left child.
   • Otherwise, peek at the stack top:
     • If right child exists and was not last visited, move to right child.
     • Otherwise, pop the node, append ")", mark it as last visited.
3. Remove the outer parentheses from the result and return.

# 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:
        if not root:
            return ""

        res = []
        stack = []
        last_visited = None
        cur = root

        while cur or stack:
            if cur:
                res.append(f"({cur.val}")
                if not cur.left and cur.right:
                    res.append("()")

                stack.append(cur)
                cur = cur.left
            else:
                top = stack[-1]
                if top.right and last_visited != top.right:
                    cur = top.right
                else:
                    stack.pop()
                    res.append(")")
                    last_visited = top

        return "".join(res)[1:-1]

Time & Space Complexity

• Time complexity: $O(n)$
• Space complexity: $O(n)$

---

Common Pitfalls

Omitting Empty Parentheses for Missing Left Child

When only the right child exists, you must include empty parentheses () for the missing left child to preserve tree structure. Without this, the right child would be incorrectly interpreted as the left child during reconstruction.

# Wrong: Missing empty parentheses
if right:
    return f"{cur}({right})"  # Output: "1(3)" instead of "1()(3)"

# Correct: Include empty parentheses for missing left
if right:
    return f"{cur}()({right})"

Adding Unnecessary Parentheses for Missing Right Child

When only the left child exists, you should NOT add empty parentheses for the missing right child. The problem specifically states that empty parentheses for missing right children should be omitted since they don't affect tree reconstruction.