LeetCode 606: Construct String from Binary Tree Solution in Python – A Step-by-Step Guide

What Is LeetCode 606: Construct String from Binary Tree?

In LeetCode 606: Construct String from Binary Tree, you’re given a binary tree where each node has a value, and your task is to convert it into a string using preorder traversal (root, left, right). The rules are: include the root value, and for each non-null child, wrap its subtree in parentheses—but skip parentheses for a missing right child if there’s no left child. For example, a tree with root 1, left 2 (with left 4), and right 3 becomes "1(2(4))(3)". This problem tests your ability to traverse trees and manage string construction with specific formatting.

Problem Statement

• Input: A binary tree (root node with val, left, right attributes).
• Output: A string representing the tree.
• Rules:
• Use preorder: root, then left, then right.
• Root value as is.
• Left child’s subtree in () if present.
• Right child’s subtree in () if present, but omit if no left child and no right child.

Constraints

• Number of nodes: 1 to 10⁴.
• Node values: -1000 to 1000.
• Tree height: ≤ 1000.

Examples

• Input: [1,2,3,4] (1->2(left)->4(left), 1->3(right))
• Output: "1(2(4))(3)"
• Input: [1,2,3,null,4] (1->2(left)->4(right), 1->3(right))
• Output: "1(2()4)(3)"
• Input: [1,null,2] (1->2(right))
• Output: "1()2"

These examples show the pattern—let’s build it!

Understanding the Problem: Stringing the Tree

To solve LeetCode 606: Construct String from Binary Tree in Python, we need to traverse a binary tree and construct a string that reflects its structure, following preorder (root-left-right) and the parentheses rules. A naive approach might overcomplicate parentheses, but we can streamline it. We’ll use:

• Best Solution (Recursive Preorder): O(n) time, O(h) space (h = tree height)—simple and natural.
• Alternative Solution (Iterative Stack): O(n) time, O(n) space—explicit control.

Let’s start with the recursive solution, breaking it down for beginners.

Best Solution: Recursive Preorder Traversal

Why This Is the Best Solution

The recursive preorder approach is the top pick for LeetCode 606 because it’s efficient—O(n) time to visit each node once—and mirrors the natural structure of tree traversal. It’s clean, intuitive, and handles parentheses rules elegantly with minimal code. It’s like telling a story about the tree, starting at the root and branching out!

How It Works

Think of this as narrating the tree’s layout:

• Step 1: Base Case:
• If node is None, return empty string.
• Step 2: Root:
• Start with the node’s value as a string.
• Step 3: Left Child:
• If left exists, append (left_subtree).
• If no left, append nothing (or () if right exists).
• Step 4: Right Child:
• If right exists, append (right_subtree).
• Skip if no right and no left.
• Step 5: Recurse:
• Call the function on left and right children.

It’s like writing a tree diary—root first, then kids!

Step-by-Step Example

Example: [1,2,3,4] (1->2(left)->4(left), 1->3(right))

• Root 1:
• Start: "1".
• Left: 2 exists, recurse.
• Node 2:
• "2".
• Left: 4 exists, "2(4)".
• Right: None, "2(4)".
• Back to 1:
• "1(2(4))".
• Right: 3 exists, "1(2(4))(3)".
• Node 3:
• "3", no children, "3".
• Final: "1(2(4))(3)".

Code with Detailed Line-by-Line Explanation

Here’s the Python code, explained clearly:

Copy codeclass 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: TreeNode) -> str:
        # Step 1: Base case
        if not root:
            return ""

        # Step 2: Start with root value
        result = str(root.val)

        # Step 3: Handle left child
        if root.left:
            result += "(" + self.tree2str(root.left) + ")"
        elif root.right:  # No left but right exists
            result += "()"

        # Step 4: Handle right child
        if root.right:
            result += "(" + self.tree2str(root.right) + ")"

        # Step 5: Return constructed string
        return result

• Lines 1-5: TreeNode class (standard).
• Lines 10-11: Base case: empty string for null.
• Line 14: Root value as string.
• Lines 17-19: Left:
• If left, recurse and wrap in ().
• If no left but right, add ().
• Lines 22-23: Right:
• If right, recurse and wrap in ().
• Time Complexity: O(n)—visit each node once.
• Space Complexity: O(h)—recursion stack (h = height).

This is like a tree storyteller—simple and smooth!

Alternative Solution: Iterative Stack-Based Approach

Why an Alternative Approach?

The iterative stack-based method uses a stack to mimic preorder traversal—O(n) time, O(n) space. It’s more explicit, giving you control over the process, and avoids recursion, which some find tricky. It’s like manually walking the tree with a notepad!

How It Works

Picture this as a tree hike with a stack:

• Step 1: Push root and track visited nodes.
• Step 2: Process stack:
• Pop node, add value.
• Handle left and right with parentheses.
• Push right, then left (preorder order).
• Step 3: Build string as you go.
• Step 4: Handle edge cases (e.g., no left but right).

It’s like a step-by-step tree scribe!

Step-by-Step Example

Example: [1,2,3,4]

• Init: Stack = [(1, False)], result = "".
• Pop (1, False):
• result = "1", mark visited.
• Push (3, False), (2, False).
• Pop (2, False):
• result = "1(2", push (4, False).
• Pop (4, False):
• result = "1(2(4", no children.
• Close: result = "1(2(4)".
• Pop (3, False):
• result = "1(2(4))(3", no children.
• Close: result = "1(2(4))(3)".
• Final: "1(2(4))(3)".

Code for Iterative Approach

Copy codeclass Solution:
    def tree2str(self, root: TreeNode) -> str:
        if not root:
            return ""

        stack = [(root, False)]  # (node, visited)
        result = []

        while stack:
            node, visited = stack.pop()
            if visited:
                result.append(")")
            else:
                result.append(str(node.val))
                stack.append((node, True))  # Mark to close later
                if node.right:
                    stack.append((node.right, False))
                if node.left:
                    stack.append((node.left, False))
                elif node.right:
                    result.append("()")

        return "".join(result)

• Lines 6-7: Start with root, empty result.
• Lines 9-19: Process stack:
• Visited: Close with ).
• Not visited: Add value, push to close later.
• Push right, then left (preorder).
• Add () if no left but right.
• Time Complexity: O(n)—visit each node.
• Space Complexity: O(n)—stack size.

It’s a manual tree walk—detailed but clear!

Comparing the Two Solutions

• Recursive (Best):
• Pros: O(n) time, O(h) space, clean and concise.
• Cons: Recursion depth for very tall trees.
• Iterative (Alternative):
• Pros: O(n) time, O(n) space, no recursion.
• Cons: More code, higher space.

Recursive wins for simplicity.

Additional Examples and Edge Cases

• Input: [1]
• Output: "1".
• Input: [1,null,2]
• Output: "1()2".

Both handle these well.

Complexity Breakdown

• Recursive: Time O(n), Space O(h).
• Iterative: Time O(n), Space O(n).

Recursive is leaner.

Key Takeaways

• Recursive: Natural tree flow—smart!
• Iterative: Stack control—clear!
• Trees: Traversal is fun.
• Python Tip: Strings build easy—see Python Basics.

Final Thoughts: String That Tree

LeetCode 606: Construct String from Binary Tree in Python is a cool tree-to-string puzzle. Recursive preorder offers elegance, while iterative gives hands-on control. Want more? Try LeetCode 94: Binary Tree Inorder Traversal or LeetCode 144: Binary Tree Preorder Traversal. Ready to encode? Head to Solve LeetCode 606 on LeetCode and string that tree today!