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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Construct Binary Tree from String

Number: 536

Difficulty: Medium

Paid? Yes

Companies: Meta, Amazon

Problem Description

Given a string representing a binary tree in a parenthesis-based format, construct the corresponding binary tree. The string starts with an integer (which can be negative) representing the root node's value, followed by zero, one, or two pairs of parentheses. Each pair of parentheses encloses a subtree, with the left child always constructed before the right child if both exist.

Key Insights

  • The input string uses parentheses to denote the boundaries of left and right subtrees.
  • A recursive or iterative (using a stack) approach can be used to parse the string.
  • The first integer encountered, before any parenthesis, is the root node's value.
  • Matching each opening parenthesis with its corresponding closing parenthesis is crucial; a stack can help or you can use recursive counting.
  • The algorithm must handle negative numbers as well as multi-digit integers.

Space and Time Complexity

Time Complexity: O(n), where n is the length of the string, as each character is processed once. Space Complexity: O(n), in the worst case the recursion stack or the explicit stack can store nearly all characters.

Solution

We can solve the problem using a recursive approach that parses the string from left to right. The algorithm works as follows:

  1. Start by reading the integer at the current position to create a new tree node.
  2. If the next character is an opening parenthesis, recursively construct the left subtree.
  3. After processing the left subtree, check again for another opening parenthesis; if one exists, recursively construct the right subtree.
  4. The recursion terminates when the end of the string or a closing parenthesis is encountered.
  5. Key trick: when parsing subtrees, ensure proper matching of parentheses by tracking the current index during the recursive calls.

Data Structures:

  • A tree node class/structure to store the value and pointers/references to left and right child nodes.
  • The recursion implicitly uses a call stack to handle the nested subtrees.

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

class Solution:
    def str2tree(self, s: str) -> TreeNode:
        # Recursive helper function that returns the node and updated index
        def helper(index: int) -> (TreeNode, int):
            if index >= len(s):
                return None, index
            
            # Parse the integer (handle negative numbers)
            sign = 1
            if s[index] == '-':
                sign = -1
                index += 1
            
            num = 0
            while index < len(s) and s[index].isdigit():
                num = num * 10 + int(s[index])
                index += 1
            node = TreeNode(sign * num)
            
            # Process left child if there is an opening parenthesis
            if index < len(s) and s[index] == '(':
                node.left, index = helper(index + 1)  # Skip '('
                index += 1  # Skip ')'
            
            # Process right child if there is another opening parenthesis
            if index < len(s) and s[index] == '(':
                node.right, index = helper(index + 1)  # Skip '('
                index += 1  # Skip ')'
            
            return node, index
        
        root, _ = helper(0)
        return root

# Example usage:
# sol = Solution()
# tree = sol.str2tree("4(2(3)(1))(6(5)(7))")
← Back to All Questions