Given a string consisting of parenthesis and integers, the whole input represents a binary tree.
The integer represents the root's value and a pair of parenthesis contains a child binary tree with the same structure.
If only one child is given, assume it as left child.
The task is to construct a binary tree from the given string and print it's nodes in level order.
Example 1: Construct a binary tree from the given string
Input: 1(2)(3)
Output: 1, 2, 3
1
/ \
2 3
Example 2: Construct a binary tree from the given string
Input: 1(2(4)(5))(3(6))
Output: 1, 2, 3, 4, 5, 6
1
/ \
2 3
/ \ /
4 5 6
Solutions
Method 1: Using stack
Observing closely we can find that, the very first character in the string is the "root".
Starting from the second character to the end, the string contains one or two set of "()", representing left and right sub-tree.
We need to find substrings representing left & right subtrees and recur the process.
We need to find the index of first ")", and this can be done using a Stack.