Construct Binary Tree from String with bracket representation

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

You can also try this code with Online C++ Compiler

Run Code

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