Construct String from Binary Tree — Preorder with Parentheses

Problem Statement#

Given the root of a binary tree, construct a string consisting of parentheses and integers from a binary tree following preorder traversal. Omit all empty parenthesis pairs only when omitting them does not break the one-to-one mapping between the string and the original tree.

Constraints:

• Number of nodes is in [1, 10^4]
• -1000 <= Node.val <= 1000

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

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

Why This Problem Matters#

LeetCode 606 "Construct String from Binary Tree" is an Amazon and Apple favorite for warming up tree serialization fluency. It looks easy but trips up many candidates because of the asymmetric rule: an empty right subtree can be dropped, but an empty left subtree must be preserved as () to disambiguate.

Mastering this teaches the foundational skill behind harder problems like Serialize/Deserialize Binary Tree (LC 297) and helps reason about ambiguous representations in compilers, ASTs, and parsers.

The Core Insight#

Think of the encoding as a recursive template. For a node with value v:

• If both children are null → "v"
• If only the right is null → "v(L)" (drop empty right paren)
• If only the left is null → "v()(R)" (must keep empty left paren)
• If both exist → "v(L)(R)"

The asymmetry exists because positional meaning matters: without (), the parser would mistake the right child for a left child.

Visual Dry Run#

Tree [1,2,3,null,4]:

    1
   / \
  2   3
   \
    4

Solution (Optimal)#

class Solution:
    def tree2str(self, root):
        if not root:
            return ""
        if not root.left and not root.right:
            return str(root.val)
        if not root.right:
            return f"{root.val}({self.tree2str(root.left)})"
        return f"{root.val}({self.tree2str(root.left)})({self.tree2str(root.right)})"

var tree2str = function(root) {
    if (!root) return "";
    if (!root.left && !root.right) return String(root.val);
    if (!root.right) return `${root.val}(${tree2str(root.left)})`;
    return `${root.val}(${tree2str(root.left)})(${tree2str(root.right)})`;
};

Time: O(n) — visit every node once; string concatenation is amortized linear here because each character contributes once. Space: O(h) recursion plus O(n) for the output string.

Common Mistakes#

• Dropping the empty () for a missing left child, breaking the one-to-one mapping.
• Wrapping the entire expression in extra parentheses around the root.
• Returning early on right being null without checking left first — the order of conditions matters.
• Using string concatenation in a tight loop in languages where that is quadratic. Prefer a string builder or join.
• Forgetting the empty-tree base case root is None.

Interview Tips#

• Mention the asymmetry between left and right early. It signals you read the constraints.
• Show the four cases on the whiteboard before writing code — it forces you to think through them.
• For very large trees, switch to an explicit stack to avoid recursion depth limits.
• Practice the inverse: parsing the string back into a tree is a common follow-up.

Follow-up Questions#

• Inverse problem (LC 536): parse "4(2(3)(1))(6(5))" back into a tree. Hint: stack of nodes plus parent tracking.
• N-ary version: serialize an N-ary tree similarly. Hint: list children inside parentheses.
• No empty parens at all: redefine to drop empty left parens too — what extra delimiter do you need? Hint: comma between children.
• Iterative version: convert the recursion to an explicit stack. Hint: emulate a preorder DFS.
• Streaming output: print as you traverse without building the full string. Hint: pass an output stream.

Key Takeaways#

• LeetCode 606 hinges on knowing when to drop empty parentheses.
• Empty right parens can be dropped; empty left parens must remain.
• Four template cases: leaf, only-left, only-right (drop), both children.
• O(n) time and O(n) output size — recursion adds O(h) stack.
• Inverse parsing (LC 536) is a natural and common follow-up.
• Foundational skill for Serialize/Deserialize Binary Tree (LC 297).
• Asked at Amazon and Apple as a warm-up tree problem in onsite rounds.