Last Updated: 22 Jan, 2021

Convert ternary expression to a binary tree.

Easy

Asked in companies

Solve now

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).

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

Solve now

Approaches

01 Approach

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

Solve now

02 Approach

As the associativity of the ternary operator is from right to left, we can build a solution starting from the end of the string.

The steps are as follows:

Let’s say we have given a string ‘STR’ of size ‘N’.
Let’s take a stack say ‘S’ (which will store nodes of the tree).
Make a node with the last character and push it to ‘S’.
Iterate over the ‘STR’ for ‘N’ - 2 >= ‘i’ >= 0 and do:
- If ‘STR[i]’ is a special character then continue iterating.
- If 'STR[i]' is an alphabet then do:
  - Make a node with the current character say 'ROOT'.
  - If 'STR[i+1]' is equal to ‘?’ then do:
    - If the size of the stack is equal to 1:
      - Extract top element from stack says 'FIRST'.
      - Set 'ROOT'->left = 'FIRST'.
    - Else
      - Extract top two elements from stack say ‘FIRST’ and ‘SECOND’.
      - Set 'ROOT'->left = ‘FIRST’.
      - Set 'ROOT'->right = 'SECOND'.
    - Push ‘ROOT’ to ‘S’.
  - 'If STR[i+1]' is equal to ‘:’ then do:
    - Push ‘ROOT’ to ‘S’.
Return the top element of the stack which will be the root of the tree.

Solve now