1.
Introduction
2.
Examples
2.1.
Algorithm
2.2.
Code
2.3.
Output
2.4.
Time complexity
2.5.
Space complexity
3.
3.1.
What exactly is a perfect binary tree?
3.2.
How can the total number of nodes in a binary tree be determined?
3.3.
How many nodes are there in a complete binary tree?
3.4.
Describe a hash table.
3.5.
What does a binary tree's level mean?
4.
Conclusion
Last Updated: Mar 27, 2024
Medium

# Construct Binary Tree from String with bracket representation

Ankit Kumar
0 upvote
Roadmap to SDE career at Amazon
Speaker
Anubhav Sinha
SDE-2 @
25 Jun, 2024 @ 01:30 PM

## 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 pre-order 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

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

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

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

4. Declare a stack.

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

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

7. Store the index in the index variable.

8. Recursively call the substring containing the left subtree.

9. 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;
}
}
}
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.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

### What exactly is a perfect binary tree?

If every leaf node is at the same level and every internal node has precisely two children, then the binary tree is said to be perfect. All internal nodes share the degree of 2.

### How can the total number of nodes in a binary tree be determined?

Move over the left subtree, tally the nodes, and save the result in the sumLeft variable if the tree is not empty. Go to the right subtree, add up all the nodes, and then keep the total in sumRight. Add the temp data, sumLeft, and sumRight to determine the final total.

### How many nodes are there in a complete binary tree?

In each instance, the number of nodes is n, and the tree's height is h. A perfect binary tree of height h has nodes that are 2h + 1 - 1 as its nodes.

### Describe a hash table.

Data structures that store information associatively include hash tables. A hash table stores data in an array format, with each data value having a distinct index value.

### What does a binary tree's level mean?

In a binary tree, the root node is the node at the top. A node's level is determined by the number of edges along the distinctive path connecting it to the root node.

## Conclusion

In this article, we discussed how to construct a binary tree from a given string with bracket representation, and we saw the algorithm for the problem. Then its implementation followed in C++. We also discussed the time and space complexity of the code.

Recommended problems -

You can also refer to our Guided Path on Coding Ninjas Studio to upskill yourself in Data Structures and AlgorithmsCompetitive Programming,

Happy learning!

Live masterclass