Convert ternary expression to a binary tree.

Easy
0/40
Average time to solve is 15m
profile
Contributed by
5 upvotes
Asked in companies
FacebookGrabGroww

Problem statement

You are given a ternary expression in the form of a string. Your task is to convert this expression into a binary tree.

Note: 
1. The string is made up of lowercase English alphabets,  ‘?’ and ‘:’ special characters.

2. The alphabets may be repeated in the string.

3. The expression which uses ‘?:’ is known as ternary expression and the expression will be evaluated as (condition ? value_if_true : value_if_false).
Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line of input contains a single integer 'T', representing the number of test cases.

The first and the only line of each test case contains a string 'STR' representing the ternary expression.
Output format: 
For each test case, return the level order traversal of the resultant binary tree in a space separated elements in a single line . If a node is NULL then # will be considered at its place.
Note : 
You don’t have to print anything, it has already been taken care of. Just implement the given function.
Constraints: 
1 <= T <= 100
1<= N <= 10^4

Where ‘N’ is the length of the string.

Time limit: 1 sec

Sample Input 1:

2
a?b:c
a?b?c:d

Sample Output 1 :

a b c # # # #
a b # c d # # # #

Explanation for Sample Output 1:

In test case 1, The tree for the string will be:

altImage

In test case 2, The tree for the string will be:

altImage

Sample Input 2:
2
j?k:l?m:o
m?n?p:o?o
Sample Output 2:
j k l # # m o # # # #
m n # p o # # o # # #
Explanation for Sample Output 2:
In test case 1, The tree for the string will be:

altImage

 In test case 2,The tree for the string will be:

altImage

Hint

Think about recursion.

Approaches (2)
Recursion

The idea is to use recursion and the tree will be built in a bottom-up approach. As for each node, we need to find its left and right child, but the child will have to find their children first and only then they can be assigned to their parent.

 

The steps are as follows:

 

  • Let’s say we have a helper function named ‘SOLVE’ which will get a string ('STR'), and index as parameters('IDX'), here 'IDX' will be passed as a reference and will be initialized to 0.
  • The following steps will be repeated in ‘SOLVE’ function.
  • Make a node ‘ROOT’(Node with a value equal to ‘STR[IDX]’ and left and right child as NULL).
  • Base condition:
    • If ‘IDX’ is greater than or equal to the length of ‘STR’ then return NULL.
    • If ‘IDX’ is equal to the length of ‘STR’ - 1 then return ‘ROOT’.
  • Recursive calls :
    • If ‘STR[IDX+1]’ = ‘?’ do:
      • Set 'IDX' = ‘IDX’ + 2
      • ROOT->left = Make a call to SOLVE with updated IDX.
      • The value of 'IDX' will be updated by the previous step as we have passed ‘IDX’ by reference.
      • Set ‘IDX’ = ‘IDX’ + 1
      • ‘ROOT’->right = Make a call to ‘SOLVE’ with updated ‘IDX’.
      • Return the ‘ROOT’.
    • If  'STR[IDX+1]' = ‘:’ do:
      • Set ‘IDX’ = ‘IDX’ + 1
      • Return the ‘ROOT’.
  • So the helper function will return us the root of the tree and now we can return the ‘ROOT’.
Time Complexity

O(N), Where ‘N' is the length of the string.

 

Since we are traversing the string only once and thus the time complexity will be O(N).

Space Complexity

O(N), Where N is the length of the string.

 

Since the total number of calls made by recursion will be equal to the number of times ‘?’ will appears. And ‘?’ can appear max of N/2 times, in the case of a skew tree. Thus the space complexity will be O(N).

Code Solution
(100% EXP penalty)
Convert ternary expression to a binary tree.
Full screen
Console