Practice/Meta/Leetcode 536. Construct Binary Tree from String

Leetcode 536. Construct Binary Tree from String

CodingMust

Problem

You are given a string that encodes a binary tree using a special parenthesized notation. Your task is to reconstruct and return the root of the binary tree from this string representation.

The encoding format follows these rules:

• Each node value is an integer (which may be negative or multi-digit)
• If a node has children, they appear immediately after the node value in parentheses
• The first set of parentheses (if present) contains the left subtree
• The second set of parentheses (if present) contains the right subtree
• Empty parentheses can be omitted, but if only a right child exists, you must include empty parentheses for the left child

For example, the string "4(2(3)(1))(6(5))" represents:

4 / \ 2 6 / \ / 3 1 5

Requirements

1. Parse the string to extract node values (handling negative numbers and multi-digit numbers)
2. Correctly identify and match opening and closing parentheses to determine subtree boundaries
3. Build the tree recursively or iteratively, ensuring left children come from the first parenthesized section and right children from the second
4. Return the root of the constructed tree
5. Handle edge cases like single-node trees and empty strings

Constraints

• 0 ≤ length of string ≤ 30,000
• Node values are integers in the range [-1000, 1000]
• The string is guaranteed to be a valid encoding of a binary tree
• Time complexity should be O(n) where n is the length of the string
• Space complexity should be O(h) where h is the height of the tree (for recursion stack or explicit stack)

Examples

Example 1:

Input: s = "4(2(3)(1))(6(5))" Output: TreeNode with root value 4 4 / \ 2 6 / \ / 3 1 5 Explanation: The root is 4. Its left child is 2 (which has left child 3 and right child 1). Its right child is 6 (which has left child 5).

Example 2:

Input: s = "1(2)(3)" Output: TreeNode with root value 1 1 / \ 2 3 Explanation: Root 1 has left child 2 and right child 3.

Example 3:

Input: s = "-10(-5)(-20)" Output: TreeNode with root value -10 -10 / \ -5 -20 Explanation: Negative numbers are handled correctly.

Example 4:

Input: s = "7" Output: TreeNode with root value 7 7 Explanation: A single node with no children.