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.

##### Complexity

**O(n**and space complexity is

^{2})**O(n)**due to auxiliary stack.