LeetCode 606 - Construct String from Binary Tree

This problem asks us to convert a binary tree into a string using a very specific preorder traversal format. We must visit nodes in the order root → left subtree → right subtree, and represent the structure of the tree using parentheses.

leetcodemediumstringtreedepth-first-searchbinary-tree

LeetCode Problem 606

Difficulty: 🟡 Medium
Topics: String, Tree, Depth-First Search, Binary Tree

Solution

Problem Understanding

This problem asks us to convert a binary tree into a string using a very specific preorder traversal format. We must visit nodes in the order root → left subtree → right subtree, and represent the structure of the tree using parentheses.

Each node contributes its integer value to the final string. If a node has children, those children are wrapped in parentheses immediately after the node value. The left child always appears before the right child.

The subtle challenge comes from how empty children are handled. In most cases, empty parentheses should be omitted to keep the string compact. However, there is one important exception: when a node has a right child but no left child, we must explicitly include () for the missing left child. Without this placeholder, the structure of the tree would become ambiguous.

For example, consider this tree:

    1
   / \
  2   3
 /
4

A complete representation with every possible pair of parentheses would look like:

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

However, unnecessary empty parentheses are removed, producing:

1(2(4))(3)

Now consider this tree:

    1
   / \
  2   3
   \
    4

The node 2 has a right child but no left child. We must preserve this missing left child explicitly:

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

The input is the root node of a binary tree. The output is a string that uniquely represents that tree while following the omission rules.

The constraints tell us that the tree can contain up to 10^4 nodes. This is large enough that we should avoid repeatedly concatenating immutable strings inefficiently, because that can lead to quadratic behavior. A linear traversal is preferable. Node values range from -1000 to 1000, but since we are simply converting integers to strings, value magnitude is not a major concern.

Several edge cases are important:

  • A tree with only one node should return just the node value with no parentheses.
  • A node with only a left child should include only the left subtree parentheses.
  • A node with only a right child must include an empty () before the right subtree.
  • Deep trees could stress recursive depth and string construction efficiency.

Approaches

Brute Force Approach

A straightforward brute-force solution is to recursively build the string using repeated string concatenation.

At each node, we recursively compute the left subtree string and the right subtree string. Then we combine them into the correct format according to the problem rules. Since Python strings and Go strings are immutable, every concatenation creates a new string. If the tree is very large, repeated concatenations can become expensive because previously built portions of the string are copied again and again.

This approach is logically correct because preorder traversal naturally matches the required output format. We process the current node first, then append the left subtree representation, then the right subtree representation. The omission rules are applied based on whether children exist.

However, naïve string concatenation can degrade performance, especially for skewed trees where concatenation repeatedly copies increasingly large strings.

Optimal Approach

The key observation is that the problem naturally maps to a depth-first traversal, specifically preorder traversal. Instead of repeatedly concatenating immutable strings, we can build the result incrementally using a list (Python) or strings.Builder (Go).

The idea is to traverse the tree recursively and append pieces of the result directly into a mutable buffer:

  • Add the node value.
  • If the node has children, process the left subtree inside parentheses.
  • If the node has a right child but no left child, explicitly append ().
  • Process the right subtree inside parentheses if it exists.

This avoids repeated copying and ensures each node contributes to the final string exactly once.

Approach Time Complexity Space Complexity Notes
Brute Force O(n²) O(n) Recursive traversal with repeated immutable string concatenation
Optimal O(n) O(n) DFS traversal with efficient mutable string building

Here, n is the number of nodes in the tree.

Algorithm Walkthrough

  1. Create a recursive DFS helper function

We use preorder traversal because the problem explicitly requires the current node to appear before its children. The helper function processes one node at a time. 2. Append the current node value

When visiting a node, immediately add its integer value to the result.

For example:

Node = 1
Result = "1"
  1. Handle the left child

If the node has a left child, wrap its recursive result inside parentheses.

Example:

Node = 2
Left child = 4

Result becomes:
"2(4)"
  1. Handle the special missing-left-child case

If the node does not have a left child but does have a right child, append:

()

This preserves the one-to-one mapping between the string and tree structure. 5. Handle the right child

If the node has a right child, recursively process it inside parentheses. 6. Continue recursively

The recursion naturally processes the entire tree in preorder order. 7. Join the accumulated pieces

In Python, we store string fragments in a list and call "".join() at the end. In Go, we use strings.Builder to efficiently accumulate characters.

Why it works

The algorithm works because it exactly mirrors the preorder traversal requirement of the problem. Every node is visited in the correct order, and the parenthesis rules are applied consistently based on child existence. The special case for a missing left child preserves structural uniqueness, ensuring the resulting string can always reconstruct the original tree unambiguously.

Python Solution

# 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

from typing import Optional

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

        def dfs(node: Optional[TreeNode]) -> None:
            if not node:
                return

            parts.append(str(node.val))

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

                if node.left:
                    dfs(node.left)

                parts.append(")")

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

        dfs(root)
        return "".join(parts)

The implementation uses a parts list to efficiently accumulate string fragments. Instead of repeatedly concatenating strings, each piece is appended to the list and combined once at the end.

The recursive dfs() function performs preorder traversal. First, it appends the current node value. Then it checks whether parentheses are needed for the left child. Notice that the condition:

if node.left or node.right:

is essential. Even if the left child is missing, we still open and close parentheses if a right child exists. This correctly produces () for the missing left subtree.

Finally, if a right child exists, it is recursively processed inside its own parentheses.

Go Solution

import (
	"strconv"
	"strings"
)

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func tree2str(root *TreeNode) string {
	var builder strings.Builder

	var dfs func(node *TreeNode)

	dfs = func(node *TreeNode) {
		if node == nil {
			return
		}

		builder.WriteString(strconv.Itoa(node.Val))

		if node.Left != nil || node.Right != nil {
			builder.WriteByte('(')

			if node.Left != nil {
				dfs(node.Left)
			}

			builder.WriteByte(')')
		}

		if node.Right != nil {
			builder.WriteByte('(')
			dfs(node.Right)
			builder.WriteByte(')')
		}
	}

	dfs(root)

	return builder.String()
}

The Go implementation follows the same logic as the Python version but uses strings.Builder for efficient string construction. Since Go strings are immutable, repeatedly concatenating with + would be inefficient for large trees.

Go uses nil instead of None for missing children, and strconv.Itoa() converts integers into strings. Parentheses are added using WriteByte() for efficiency.

Worked Examples

Example 1

Input:

root = [1,2,3,4]

Tree:

    1
   / \
  2   3
 /
4

Traversal state:

Step Current Node Result
1 1 "1"
2 2 "1(2"
3 4 "1(2(4"
4 End of 4 "1(2(4)"
5 End of 2 "1(2(4))"
6 3 "1(2(4))(3"
7 End of 3 "1(2(4))(3)"

Final result:

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

Example 2

Input:

root = [1,2,3,null,4]

Tree:

    1
   / \
  2   3
   \
    4

Traversal state:

Step Current Node Result
1 1 "1"
2 2 "1(2"
3 Missing left "1(2()"
4 4 "1(2()(4"
5 End of 4 "1(2()(4))"
6 3 "1(2()(4))(3"
7 End of 3 "1(2()(4))(3)"

Final result:

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

Complexity Analysis

Measure Complexity Explanation
Time O(n) Every node is visited exactly once
Space O(n) Recursive call stack and output storage

The time complexity is O(n) because each node contributes its value and parentheses to the output exactly once. No node is revisited, and string assembly is efficient due to mutable buffering.

The space complexity is O(n) because the recursion stack may grow to the height of the tree in the worst case, and the output string itself also requires linear space.

Test Cases

# Definition for testing
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

solution = Solution()

# Example 1
root = TreeNode(1,
    TreeNode(2, TreeNode(4)),
    TreeNode(3)
)
assert solution.tree2str(root) == "1(2(4))(3)"  # standard balanced tree

# Example 2
root = TreeNode(1,
    TreeNode(2, None, TreeNode(4)),
    TreeNode(3)
)
assert solution.tree2str(root) == "1(2()(4))(3)"  # right child without left child

# Single node
root = TreeNode(5)
assert solution.tree2str(root) == "5"  # minimal tree

# Only left child
root = TreeNode(1, TreeNode(2))
assert solution.tree2str(root) == "1(2)"  # omit unnecessary right child parentheses

# Only right child
root = TreeNode(1, None, TreeNode(2))
assert solution.tree2str(root) == "1()(2)"  # preserve missing left child

# Negative values
root = TreeNode(-1,
    TreeNode(-2),
    TreeNode(-3)
)
assert solution.tree2str(root) == "-1(-2)(-3)"  # handles negative integers

# Deep left-skewed tree
root = TreeNode(1,
    TreeNode(2,
        TreeNode(3,
            TreeNode(4)
        )
    )
)
assert solution.tree2str(root) == "1(2(3(4)))"  # deep recursion

# Mixed missing children
root = TreeNode(1,
    TreeNode(2, None, TreeNode(4)),
    TreeNode(3, TreeNode(5))
)
assert solution.tree2str(root) == "1(2()(4))(3(5))"  # multiple subtree shapes
Test Why
[1,2,3,4] Validates standard preorder formatting
[1,2,3,null,4] Verifies required empty () for missing left child
Single node Confirms no unnecessary parentheses
Only left child Ensures omitted empty right child
Only right child Tests special structural preservation rule
Negative values Verifies integer conversion works correctly
Left-skewed tree Tests deep recursive traversal
Mixed missing children Validates multiple edge cases simultaneously

Edge Cases

A tree containing only a single node is an important boundary case. A naïve implementation might accidentally wrap the node in unnecessary parentheses such as "1()". The correct output is simply the node value. This implementation handles the case naturally because parentheses are only added when children exist.

A node with only a right child is the most error-prone scenario in the problem. If we omit the empty left parentheses, the structure becomes ambiguous. For example, "1(2)" could mean a left child or a right child. The implementation explicitly checks:

if node.left or node.right:

which guarantees () is inserted whenever a right child exists without a left child.

Deep skewed trees are another potential source of issues. Since the tree may contain up to 10^4 nodes, inefficient string concatenation could become very slow. Using a list of string fragments in Python and strings.Builder in Go ensures linear performance, avoiding repeated copying of large intermediate strings.