Introduction
The problem statement is constructing a binary tree from a given string with bracket representation. The input will be in the form of an integer depicting the binary tree's root value. The integer is followed by a set of parenthesis which contains the value of the child of the root node in order of left child first and right child second. The output should be a binary tree with properly arranged node values.
Let us see some examples of input and output for the above statement of the problem.
Examples
Input  7 (8) (9)
Output  7 8 9
The above output will be stored in a binary tree in the following format.
Explanation  The first integer in the input format holds the value of the root node, the first parenthesis has the value of its left child, and the second parenthesis indicates the value of its right child. Hence the output consists of preorder traversal of the constructed binary tree.
Let us look at one more complex example for this problem statement.
Input  1(2(3)(4))(5(6))
Output  1 2 3 4 5 6
The above output will be stored in a binary tree in the following format.
Explanation  As seen in the input, the first integer contains the root value; hence we have added one in the root node, followed by two, which is the left child of one. Again there is a parenthesis which means three and four are the child node of root node two. In the end, the right child of one is given, closed by the left child of five, six.
With the help of the above two examples, I hope the problem is clear to you. Let us now move forward and see the algorithm for solving this problem.
Algorithm

The first integer in the string is the value of the root node.

Inside the first parenthesis, the value of the left child is stored.

Inside the second parenthesis, the value of the right child is stored.

Declare a stack.

We will find the index of the first substring containing the opening parenthesis.

We will also find the index of the second substring containing the closing parenthesis.

Store the index in the index variable.

Recursively call the substring containing the left subtree.

Recursively call the substring containing the right subtree.
It is now the time to see the implementation in C++ of the discussed algorithm.
Code
//A program in C++ to construct a binary tree from the string with bracket representation.
#include <bits/stdc++.h>
using namespace std;
//Defining the structure of a binary tree.
struct Node {
int data;
Node *left, *right;
};
// A function that allocates a new node
Node* newNode(int data)
{
Node* node = (Node*)malloc(sizeof(Node));
node>data = data;
node>left = node>right = NULL;
return (node);
}
// A function to traverse the binary tree in the preorder manner
void preorder(Node* node)
{
if (node == NULL)
return;
printf("%d ", node>data);
preOrder(node>left);
preOrder(node>right);
}
// A function to find out index containing the ')'
int find_Index(string str, int si, int ei)
{
if (si > ei)
return 1;
// Inbuilt stack
stack<char> s;
for (int i = si; i <= ei; i++) {
// if open parenthesis, push it
if (str[i] == '(')
s.push(str[i]);
// if close parenthesis
else if (str[i] == ')') {
if (s.top() == '(') {
s.pop();
// if the stack is empty, this is
// the required index
if (s.empty())
return i;
}
}
}
// if not found return 1
return 1;
}
// A function to construct the tree from the given string
Node* tree_from_string(string str, int si, int ei)
{
// Base case
if (si > ei)
return NULL;
// new root
Node* root = newNode(str[si]  '0');
int index = 1;
// if the next char is '(' find the index of
// its complement ')'
if (si + 1 <= ei && str[si + 1] == '(')
index = find_Index(str, si + 1, ei);
// if index found
if (index != 1) {
// Recursive call for left subtree
root>left = tree_from_string(str, si + 2, index  1);
// Recursive call for right subtree
root>right = tree_from_string(str, index + 2, ei  1);
}
return root;
}
//Main function
int main()
{
string str = "1(2(3)(4))(5(6))";
Node* root = tree_from_string(str, 0, str.length()  1);
preorder(root);
}
Output
1 2 3 4 5 6
Time complexity
The Time complexity of the above code is O(N^2), where N is the number of elements in the binary tree.
Space complexity
The Space complexity of the above code isO(N), as it uses a stack of N size.
This marks the end of the blog, and I hope you learned how to tackle this problem in your next endeavours.
Let us see some of the faqs related to the blog.
Check out this article  Balanced Parentheses