LeetCode 606: Construct String from Binary Tree

Problem Restatement

We are given the root of a binary tree.

We need to convert the tree into a string using preorder traversal:

However, unnecessary empty parentheses should be omitted.

There is one important exception:

If a node has a right child but no left child, we must include:

()

for the missing left child.

This keeps the mapping between the string and the original tree unambiguous.

The official problem defines the serialization using preorder traversal with parentheses and requires omission of unnecessary empty pairs while preserving a one-to-one mapping between the string and the tree.

Input and Output

Function signature:

def tree2str(root: Optional[TreeNode]) -> str:
    ...

Input:

Output:

Example

Example 1:

Tree:

    1
   / \
  2   3
 /
4

Output:

"1(2(4))(3)"

Traversal process:

Example 2:

Tree:

    1
   / \
  2   3
   \
    4

Output:

"1(2()(4))(3)"

Notice the empty parentheses:

()

They are required because node 2 has no left child but does have a right child.

Without them, the structure would become ambiguous.

First Thought: Build the String During Traversal

This problem naturally matches preorder traversal.

For every node:

1. Output the node value.
2. Serialize the left subtree.
3. Serialize the right subtree.

The challenge is deciding when parentheses are required.

Key Insight

There are four structural cases.

The third case is the important one.

We must preserve the empty left subtree whenever a right subtree exists.

This makes recursion very clean.

Algorithm

Use recursive preorder traversal.

For each node:

1. Convert the node value to a string.
2. Recursively serialize the left subtree.
3. Recursively serialize the right subtree.
4. Build the result according to the four structural cases.

Base case:

• If the node is None, return an empty string.

Implementation

from typing import Optional

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 root is None:
            return ""

        value = str(root.val)

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

        if not root.left and not root.right:
            return value

        if root.left and not root.right:
            return f"{value}({left})"

        if not root.left and root.right:
            return f"{value}()({right})"

        return f"{value}({left})({right})"

Code Explanation

The recursion stops at empty nodes:

if root is None:
    return ""

Each node begins with its own value:

value = str(root.val)

Then we recursively serialize both subtrees:

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

Now we handle the four structural cases.

Case 1: Leaf Node

if not root.left and not root.right:
    return value

A leaf node has no children, so no parentheses are needed.

Case 2: Only Left Child

if root.left and not root.right:
    return f"{value}({left})"

We include the left subtree normally.

Case 3: Only Right Child

if not root.left and root.right:
    return f"{value}()({right})"

This is the special case.

We must include:

()

for the missing left subtree.

Case 4: Both Children

return f"{value}({left})({right})"

Both subtrees are included normally.

Correctness

The algorithm performs preorder traversal because each node value is output before recursively processing its left and right children.

For every node, the algorithm exactly follows the required serialization rules:

The special case:

() 

for a missing left child ensures that the resulting string preserves the original tree structure.

Without it, two different trees could produce the same serialization.

Because every subtree is serialized recursively using the same rules, the final string correctly represents the entire binary tree.

Complexity

Let n be the number of nodes.

Here, h is the tree height.

Alternative: Direct DFS Helper

We can also write the traversal using a helper function and a list builder.

class Solution:
    def tree2str(self, root: Optional[TreeNode]) -> str:

        parts = []

        def dfs(node):

            if not node:
                return

            parts.append(str(node.val))

            if node.left or node.right:
                parts.append("(")
                dfs(node.left)
                parts.append(")")

            if node.right:
                parts.append("(")
                dfs(node.right)
                parts.append(")")

        dfs(root)

        return "".join(parts)

This version avoids repeated string concatenation by collecting pieces into a list.

Testing

def run_tests():

    s = Solution()

    root1 = TreeNode(
        1,
        TreeNode(
            2,
            TreeNode(4)
        ),
        TreeNode(3)
    )

    assert s.tree2str(root1) == "1(2(4))(3)"

    root2 = TreeNode(
        1,
        TreeNode(
            2,
            None,
            TreeNode(4)
        ),
        TreeNode(3)
    )

    assert s.tree2str(root2) == "1(2()(4))(3)"

    root3 = TreeNode(1)

    assert s.tree2str(root3) == "1"

    root4 = TreeNode(
        1,
        None,
        TreeNode(2)
    )

    assert s.tree2str(root4) == "1()(2)"

    print("all tests passed")

run_tests()

Test coverage: