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:

Step	Meaning
Visit current node	Output node value
Visit left subtree	Wrap in parentheses
Visit right subtree	Wrap in parentheses

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:

Parameter	Meaning
`root`	Root node of the binary tree

Output:

Type	Meaning
`str`	Parenthesized preorder representation

Example

Example 1:

Tree:

Output:

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

Traversal process:

Node	Generated String
`4`	`"4"`
`2`	`"2(4)"`
`3`	`"3"`
`1`	`"1(2(4))(3)"`

Example 2:

Tree:

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:

Output the node value.
Serialize the left subtree.
Serialize the right subtree.

The challenge is deciding when parentheses are required.

Key Insight

There are four structural cases.

Left Child	Right Child	Output Form
None	None	`"value"`
Exists	None	`"value(left)"`
None	Exists	`"value()(right)"`
Exists	Exists	`"value(left)(right)"`

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:

Convert the node value to a string.
Recursively serialize the left subtree.
Recursively serialize the right subtree.
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:

Structure	Serialization
No children	Value only
Left child only	Value plus left subtree
Right child only	Empty left subtree plus right subtree
Both children	Both subtrees

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.

Metric	Value	Why
Time	`O(n)`	Every node is visited once
Space	`O(h)`	Recursive call stack height

Here, h is the tree height.

Tree Type	Stack Depth
Balanced tree	`O(log n)`
Skewed tree	`O(n)`

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:

Case	Why
Full binary tree	Standard recursion
Missing left child	Special empty-parentheses case
Single node	Smallest tree
Right-only subtree	Confirms structure preservation