Construct String from Binary Tree: Preorder with Parentheses

You are given the root of a binary tree and need to build a string from it using preorder traversal. Each node's value is followed by parentheses wrapping its children's subtree strings, but you should omit unnecessary empty parentheses whenever possible while keeping the representation unambiguous.

This is LeetCode 606: Construct String from Binary Tree. Given root = [1, 2, 3, 4], the output is "1(2(4))(3)". Node 2 has a left child (4) but no right child, so we skip the empty right-child parentheses. If node 2 had a right child but no left child, we would need () for the missing left child to preserve the tree structure.

Why this problem matters

This problem tests whether you understand preorder traversal well enough to extend it beyond simple node collection. Instead of just recording values in order, you are building a structured string that encodes the shape of the tree. The tricky part is knowing when to include empty parentheses and when to leave them out.

The rule is simple but easy to get wrong: you always need parentheses for the left subtree if the node has any children. You only need parentheses for the right subtree if the right child actually exists. If there is a right child but no left child, you must include empty parentheses () for the missing left child so the right child does not get mistaken for a left child.

This pattern of selectively encoding tree structure shows up in serialization and deserialization problems. If you can build this string correctly, you are already thinking about how to represent trees as strings in a way that can be decoded back.

The approach

The algorithm follows preorder traversal (root, left, right) with two rules for parentheses:

1. If a node has a left child or a right child, wrap the left subtree result in parentheses.
2. If a node has a right child, wrap the right subtree result in parentheses.

That is the entire logic. When the left child is missing but the right child exists, rule 1 still fires (because root.right is truthy), producing () for the empty left subtree. When both children are missing, neither rule fires and the node contributes only its value.

def tree2str(root):
    if not root:
        return ""

    result = str(root.val)

    if root.left or root.right:
        result += "(" + tree2str(root.left) + ")"

    if root.right:
        result += "(" + tree2str(root.right) + ")"

    return result

The recursion mirrors the tree structure. Each call handles one node, and the base case returns an empty string for None nodes. The conditional checks ensure that parentheses are only added when needed.

Step-by-step walkthrough

Complexity analysis

Time is O(n) because every node is visited exactly once during the preorder traversal.

Space is O(n) for the recursion stack in the worst case. A completely skewed tree (every node only has one child) creates a call stack n levels deep. For a balanced tree, the stack depth is O(log n). The output string itself is also O(n) in length since each node contributes a constant number of characters plus its value.

Edge cases to watch for

• Empty tree (root is None): return an empty string. The base case handles this directly.
• Single node (no children): return just the node's value as a string. Neither conditional fires, so no parentheses are added.
• Left child only: the left subtree gets wrapped in parentheses, but no right parentheses are added. For example, a root of 1 with only left child 2 produces "1(2)".
• Right child only (no left child): you must include empty parentheses for the missing left child. A root of 1 with only right child 3 produces "1()(3)". This is the case most people forget.
• Complete binary tree: every node has both children except the leaves. All internal nodes produce both sets of parentheses.

The building blocks

This problem uses one key building block:

Preorder traversal with conditional output. The standard preorder pattern is "process root, recurse left, recurse right." Here, "process root" means converting the value to a string, and the recursion adds parentheses around the child results conditionally. The same skeleton works for any problem where you need to build a string or data structure that mirrors the tree's shape from the top down.

# The general preorder-with-output pattern:
def build(node):
    if node is None:
        return ""
    result = process(node)
    if should_include_left(node):
        result += wrap(build(node.left))
    if should_include_right(node):
        result += wrap(build(node.right))
    return result

For this problem, process converts the value to a string, should_include_left checks if either child exists, should_include_right checks if the right child exists, and wrap adds parentheses around the recursive result.

From understanding to recall

You now understand the two-rule system: add left parentheses if any child exists, add right parentheses only if the right child exists. The recursion is clean and the base case is a single line. But could you write it from scratch in an interview without looking at it?

The tricky part is remembering the condition for left parentheses: if root.left or root.right. It is tempting to write if root.left and miss the case where only the right child exists. That one condition is the difference between a correct and incorrect solution.

Spaced repetition helps you internalize these subtle conditions. You write the solution from memory, get it wrong once by forgetting the or root.right part, and then you never forget it again. After a few reps, the two-rule system becomes automatic.

Related posts

• Binary Tree Preorder Traversal - The foundational traversal order that this problem builds on
• Serialize and Deserialize Binary Tree - A harder version of encoding tree structure into a string
• Binary Tree Inorder Traversal - The same recursive skeleton but with left-root-right ordering