Last Updated: 7 Feb, 2021
Binary Tree From Bracket
Easy
Asked in companies
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:
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.
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
Approaches
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