Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction 
2.
Examples
2.1.
Algorithm
2.2.
Code
2.3.
Output
2.4.
Time complexity
2.5.
Space complexity
3.
Frequently asked questions
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

Author 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.

Binary Tree Coding Ninjas

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.

binary tree representation

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.

binary tree representation

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;
     }
   }
 }
// 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

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

Frequently asked questions

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. 

See How to Find all the Palindromic Partitions of a StringRat In A MazeBinary Subarrays with sum or Reduce Array Size to The Half

 

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!

Thankyou image
Previous article
Construct a Complete Binary Tree from its Linked List Representation
Next article
Convert a Generic Tree (n-ary tree) to Binary Tree
Live masterclass