Convert ternary expression to a binary tree.

Posted: 22 Jan, 2021
Difficulty: Easy


Try Problem

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

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).
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. 
1 <= T <= 100
1<= N <= 10^4

Where ‘N’ is the length of the string.

Time limit: 1 sec
Approach 1

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’.
Try Problem