410. Construct a Binary Tree From a Bracket-Representation String

Given a binary tree written as a bracket-representation string - a node's value, optionally followed by (left-subtree) and then (right-subtree), each written the same way recursively, with an entirely absent child's parentheses omitted altogether (a node with only a left child has just one parenthesized group; a leaf has none) - reconstruct the tree and print it using level-order tokens. Print the resulting tree the same way (level order, 'N' for absent children), but omit any trailing 'N' tokens at the very end of your output.

Input: A single line containing the bracket-representation string of the tree. Output: Print the reconstructed tree as space-separated level-order tokens, omitting trailing 'N' tokens.

1 <= number of nodes <= 10^5, all values are non-negative integers

The bracket format is purely an INPUT convention here - the problem explicitly asks you to output using the standard level-order convention instead, so don't confuse the two very different serialization formats.

Parse a string like '4(2(3)(1))(6(5))' - where each node's value is optionally followed by its left and right subtrees in parentheses - back into an actual tree structure. Brute force: There isn't a meaningfully different 'brute force' here - a careful recursive-descent parser IS the natural, correct approach; the risk is in mishandling the parenthesis-matching and the 'left-only vs both children' ambiguity. Optimised: A recursive-descent parser that consumes characters left to right, recursing into each parenthesized group exactly once, naturally mirrors the string's own nested structure - each recursive call handles exactly one node's construction, giving a direct linear-time parse.

Parse the bracket string recursively: read the node's value, then if the next character is '(', find its matching ')' by scanning character by character while tracking bracket depth, slice out that substring, and recurse on it for the left child; do the same for a following '(' group for the right child. This is correct because the bracket structure is self-similar, but repeatedly slicing substrings and rescanning from scratch for every nested call means the same characters get copied and re-examined many times over. In the worst case (a long skewed chain of single-child nodes), this degrades to quadratic behaviour in both time and the memory used by the copied substrings. Time: O(n^2) Space: O(n^2)

Walk the string once character by character while maintaining an explicit stack of nodes currently being built, along with a marker for whether the next parenthesized group belongs to a node's left or right child; digits accumulate into the current number, '(' pushes the just-built node so its children can be attached, and ')' pops back up to the parent. This mirrors the recursive-descent parse exactly but replaces the implicit call stack with an explicit one on the heap, so it never risks a stack overflow even for the maximum 10^5 nodes arranged in a degenerate chain. A final BFS over the constructed tree produces the level-order output, trimming trailing 'N' tokens. Time: O(n) Space: O(n)

Instead of slicing new substrings, parse the string once left to right using a single shared position pointer that every recursive call advances directly on the original string. Each character is read exactly once no matter how deeply nested it is, so the whole string is consumed in one linear pass while still correctly recursing into left and then right subtrees per the bracket grammar. This removes all the copying overhead of the brute approach, though it still relies on the call stack, so a very skewed tree (a long chain of only-left-child nodes) can recurse as deep as there are nodes. Time: O(n) Space: O(n) worst case (recursion depth)

1. Read digits to parse the current node's value. 2. If the next character is '(', recursively parse everything inside as the LEFT child, consuming up through its matching closing ')'. 3. If ANOTHER '(' immediately follows, recursively parse that as the RIGHT child the same way - a node has zero, one (always left), or two parenthesized groups. 4. Once parsed into an actual tree, serialize it using the standard level-order format for output.

Time: O(n), where n is the length of the bracket string - each character is processed a constant number of times. Space: O(h) for the recursion stack during parsing, plus O(number of nodes) for the constructed tree.

Test with a single node and no parentheses at all, a node with only a left child (one parenthesized group, no placeholder for the missing right), and a tree with 10^5 nodes for performance.

Be precise about the 'a node with only a left child has just one parenthesized group' rule - this asymmetry (no placeholder for 'left missing, right present') is the trickiest part of the format to parse correctly.