Skip to main content

606 - Construct String from Binary Tree

Difficulty: Easy | Pattern: Tree DFS + String Building | Company tags: Amazon, Google

Problem Statement​

Given the root of a binary tree, construct a string consisting of parenthesis and integers from the binary tree with the preorder traversal way, and return it.

Omit all the empty parentheses pairs that do not affect the one-to-one mapping relationship between the string and the original binary tree.

Example 1:

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

Example 2:

Input: root = [1,2,3,null,4]
Output: "1(2()(4))(3)"
Explanation: Must include empty () for left child to preserve structure

Solution: DFS Recursive — O(n), O(h)​

Key insight:

  • If node has no children: just str(val)
  • If node has only right child: must include ()(right) — empty left parens needed
  • If node has only left child: (left) — no right parens needed (trailing empty omitted)
def tree2str(root) -> str:
    if not root:
        return ""
    
    if not root.left and not root.right:
        return str(root.val)
    
    if not root.right:
        return f"{root.val}({tree2str(root.left)})"
    
    return f"{root.val}({tree2str(root.left)})({tree2str(root.right)})"

Dry Run​

Tree: 1(root), left=2(right=4), right=3

  • tree2str(4): no children → "4"
  • tree2str(2): no right → "2(4)"
  • tree2str(3): no children → "3"
  • tree2str(1): both children → "1(2(4))(3)" ✓

Tree: 1(root), left=2(right=4 only — no left child), right=3

  • tree2str(2): has right but no left → f"2()({tree2str(4)})" = "2()(4)"
  • tree2str(1): "1(2()(4))(3)" ✓

Why Not Omit Empty Right Parens?​

1(2) is ambiguous — is 2 the left or right child? But 1()(2) clearly means: no left child, right child is 2. So trailing empty pairs (right child of rightmost node, etc.) can be omitted; internal empty pairs cannot.

Complexity​

  • Time: O(n²) — string concatenation in Python creates new strings; use list + join for O(n)
  • Space: O(h) for recursion