We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Construct String from Binary Tree

Number: 606

Difficulty: Medium

Paid? No

Companies: Meta, TikTok, Amazon, Adobe

Problem Description

Given the root of a binary tree, construct a string consisting of the node values and parentheses by performing a preorder traversal. For each node, represent its value and, if necessary, its children inside parentheses. Omit unnecessary empty parentheses except when a node has a right child but no left child—in that case, include empty parentheses to indicate the missing left child.

Key Insights

  • Use a recursive preorder traversal to visit nodes.
  • For each node, include the value directly.
  • If the node has a left child, include its string representation wrapped in parentheses.
  • If the node does not have a left child but has a right child, include empty parentheses to maintain the structure.
  • If a node has only a right child, include the left placeholder and then the right child’s representation in its own parentheses.
  • This approach guarantees a one-to-one mapping between the string and the tree.

Space and Time Complexity

Time Complexity: O(n), where n is the number of nodes, since each node is visited once. Space Complexity: O(n) in the worst case for the recursive call stack (unbalanced tree) and the string being constructed.

Solution

We solve the problem using recursion. The main idea is to perform a preorder traversal, processing each node as follows:

  1. Start with the node value as a string.
  2. Recursively obtain the string for the left child. If the left child is missing but a right child exists, append empty parentheses "()" to indicate the absence of the left subtree.
  3. Recursively obtain the string for the right child and append it in parentheses.
  4. Return the constructed string. This method correctly maintains the necessary structure and omits redundant parentheses.

Code Solutions

# 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

# Recursive function to construct the string from the binary tree.
def tree2str(root: TreeNode) -> str:
    # Base case: if the node is None, return an empty string.
    if not root:
        return ""
    
    # Start with the current node's value.
    result = str(root.val)
    
    # If either left or right child exists, process the left child.
    if root.left or root.right:
        # If left child is missing but right child exists, use empty parentheses.
        if root.left:
            result += "(" + tree2str(root.left) + ")"
        else:
            result += "()"
    
    # Process the right child if it exists.
    if root.right:
        result += "(" + tree2str(root.right) + ")"
    
    # Return the constructed string.
    return result
← Back to All Questions