Convert Ternary Expression to a Binary Tree

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;
}

You can also try this code with Online C++ Compiler

Run Code

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