## Introduction

This article will look at the problem of converting a given ternary expression into a binary tree. Binary tree questions are the most popular and vital in coding interviews and programming competitions. Let's understand the problem statement.

In computer science, a binary tree, by definition, is a tree data structure in which each node has at most 2 children, referred to as the left child and the right child.

Binary Tree example

### Problem Statement

We are given a string that contains ternary expressions. The expressions may be nested. Write a program to convert the given ternary expression to a binary Tree.

### Sample Examples

**Example 1**

```
Input 1: a?b:c
Output 1: a b c
a
/ \
b c
Explanation: The preorder traversal of the above tree is a b c.
```

**Example 2**

```
Input 2: a?b?c:d:e
Output 2: a b c d e
a
/ \
b e
/ \
c d
Explanation: The preorder traversal of the above tree is a b c d e.
```

## Approach

Since the ternary operator has associativity from right to left, the string can be traversed from right to left. We will traverse a string, then make the first character as root and do the following step recursively. If we see Symbol '?', we add the next character as the left child of root, and if we see Symbol ':', then we add it as the right child of the current root. We will do this process until we traverse all elements of string.

### Pseudocode

- Create a function to convert Ternary Expression to a Binary Tree. It returns the root of the tree.
- Write the base case that if the length of the string is exceeded we will return null.
- Store current character of string as root node.
- If current character of ternary expression is '?', then the next character is added as a left child of current node.
- Else we add it as a right child of the current node.
- Finally we will return root.

### Implementation

**Code in C++ **

```
#include <bits/stdc++.h>
using namespace std;
struct Node
{
char data;
Node *left, *right;
};
Node *newNode(char Data)
{
Node *new_node = new Node;
new_node->data = Data;
new_node->left = new_node->right = NULL;
return new_node;
}
// Function for converting Ternary Expression to a Binary Tree.
Node *convertExpression(string str, int &i)
{
// to store current character of expression_string
Node *root = newNode(str[i]);
// Base Case
if (i == str.length() - 1)
return root;
i++;
if (str[i] == '?')
{
i++; // to skip the '?'
// construct the left subtree
root->left = convertExpression(str, i);
i++; // skip the ':' character
// construct the right subtree
root->right = convertExpression(str, i);
return root;
}
else
return root;
}
// function print tree
void printTree(Node *root)
{
if (!root)
return;
cout << root->data << " ";
printTree(root->left);
printTree(root->right);
}
// Driver program to test above function
int main()
{
string expression = "a?b?c:d:e";
int i = 0;
Node *root = convertExpression(expression, i);
printTree(root);
return 0;
}
```

**Output:**

`a b c d e`

#### Complexity Analysis

**Time complexity:** O(n); where n is the length of the expression.

**Space Complexity:** O(1)

Check out this problem - __Diameter Of Binary Tree__