Binary Tree From Bracket

Easy
0/40
Average time to solve is 10m
profile
Contributed by
11 upvotes
Asked in companies
OracleIBM

Problem statement

You are given a string ‘str’ which consists of brackets and integers ∈ [1, 9]. Your task is to construct a binary tree from the given string and return the Pre-Order Traversal of it.

The rules are as follows

1. The first character of the string is guaranteed to be an integer which denotes the root element of the tree.

2. This is followed by zero, one or two pairs of parenthesis, which contains a child binary tree with the same structure.

3. The first parenthesis denotes the left child of the binary then the right child.
For Example 
Let str= “1(2)(3)”

The tree will be:

img-2

The first element i.e 1 is the root node and the first bracket signifies the left child of the root node which has only 1 element i.e 2 and the second bracket signifies the right child of the root node that has only 1 node i.e 3 . Hence we have the binary tree as shown above.
Detailed explanation ( Input/output format, Notes, Images )
Input Format 
The first line of input contains an integer ‘T’ denoting the number of test cases to run. Then the test cases follow.

The first line of each test case contains the string ‘str’.
Output Format 
For each test case, return the root node of the constructed binary tree.
The printed output is the preorder traversal of the binary tree.
Output for each test case will be printed in a new line.
Note 
You do not need to print anything; it has already been taken care of. Just implement the given function.
Constraints 
1 <= T <= 5
1 <= N <= 1000

Where 'N' denotes the length of the string 'str'

Time limit: 1 second
Sample Input 1
2
4(2(3)(1))(6(5))
4(2(3(1)))(5)
Sample Output 1
4 2 3 1 6 5 
4 2 3 1 5
Explanation of Sample Input 1
Test Case 1:

In the first test case,
We will have the following binary tree:

img-1

Test Case 2:

In the second first case we will have the following tree:

img-3

Sample Input 2
1
1(2(4)(5))(3(6)(7))
Sample Output 2
1 2 4 5 3 6 7
Approaches (1)
Brute Force Approach

The key idea in solving this problem is to construct the tree recursively and then print the pre-order traversal.

 

  • The first integer will be the root of the binary tree.
  • Then for every opening brace, we find its closing brace. We do this using a variable ‘c’ and for every opening brace i.e when str[i] is an opening brace, we increment c and for every closing brace i.e when str[c] is a closing brace we decrement c until c is zero
  • The index at which c is zero, ,is the corresponding closing brace for the opening brace and we recursively call the function for all other opening braces.
  • Once the tree is formed, we simply return the root of the tree.

 

Algorithm

 

  • We define a function construct tree which takes in the string the starting index ‘si’ and the ending index ‘ei’.
  • We make str[si] as the root node and then call a function ‘findIndex’ to find the corresponding closing brace for the opening brace using a stack.
  • Once we know the closing brace we know that the right subtree starts after the closing brace and the left subtree is in between the opening and closing brace.
  • We recursively call for the left and right subtree in the left case the ‘si’ being after the opening brace and the ‘ei’ being just before the closing brace.
  • In the right case, the opening brace will be just after the closing brace and the ending will be the last index of the string.
  • For the base case, when ‘si’>’ei’ we return the tree constructed
Time Complexity

O(N^2), where ‘N’ is the length of the string str .

 

In the worst case we can have one node in each level and the find ‘index’ is a linear function which can be called atmost ‘n’ times for making the tree. Thus overall complexity can be O(N^2)

Space Complexity

O(N), where N is the length of ‘str’.

 

The space complexity due to the recursion stack will be O(N). 

Code Solution
(100% EXP penalty)
Binary Tree From Bracket
Full screen
Console