Tutorialspoint.dev

Convert Ternary Expression to a Binary Tree

Given a string that contains ternary expressions. The expressions may be nested, task is convert the given ternary expression to a binary Tree.

Examples:

Input :  string expression =   a?b:c 
Output :        a
              /  
             b    c

Input : expression =  a?b?c:d:e
Output :     a
           /  
          b    e
        /  
       c    d

Asked In : Facebook Interview



Idea is that we traverse a string make first character as root and do following step recursively .
1. If we see Symbol ‘?’
…….. then we add next character as the left child of root.
2. If we see Symbol ‘:’
…….. then we add it as the right child of current root.
do this process until we traverse all element of “String”.

Below is the implementation of above idea

C++

// C++ program to covert a ternary expression to
// a tree.
#include<bits/stdc++.h>
using namespace std;
  
// tree structure
struct Node
{
    char data;
    Node *left, *right;
};
  
// function create a new node
Node *newNode(char Data)
{
    Node *new_node = new Node;
    new_node->data = Data;
    new_node->left = new_node->right = NULL;
    return new_node;
}
  
// Function to convert Ternary Expression to a Binary
// Tree. It return the root of tree
//Notice that we pass index i by reference because we want to skip the characters in the subtree
Node *convertExpression(string str, int & i)
{
    // store current character of expression_string 
    // [ 'a' to 'z'] 
    Node * root =newNode(str[i]);
  
    //If it was last character return
    //Base Case
    if(i==str.length()-1) return root;
  
    // Move ahead in str 
    i++;
    //If the next character is '?'.Then there will be subtree for the current node
    if(str[i]=='?')
    {
        //skip the '?'
        i++;
  
        //construct the left subtree
        //Notice after the below recursive call i will point to ':' just before the right child of current node since we pass i by reference
        root->left = convertExpression(str,i);
          
        //skip the ':' character
        i++;
  
        //construct the right subtree
        root->right = convertExpression(str,i);
        return root;
    }
    //If the next character is not '?' no subtree just return it
    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;
}

Java

// Java program to covert a ternary 
// expreesion to a tree.
import java.util.Queue;
import java.util.LinkedList;
   
// Class to represent Tree node 
class Node 
{
    char data;
    Node left, right;
   
    public Node(char item) 
    {
        data = item;
        left = null;
        right = null;
    }
}
   
// Class to covert a ternary expression to a Tree 
class BinaryTree 
{
    // Function to convert Ternary Expression to a Binary
    // Tree. It return the root of tree
    Node convertExpression(char[] expression, int i)
    {
        // Base case
        if (i >= expression.length)
            return null;
       
        // store current character of expression_string
        // [ 'a' to 'z']
        Node root = new Node(expression[i]);
       
        // Move ahead in str
        ++i;
       
        // if current character of ternary expression is '?'
        // then we add next character as a left child of
        // current node
        if (i < expression.length && expression[i]=='?')
            root.left = convertExpression(expression, i+1);
       
        // else we have to add it as a right child of
        // current node expression.at(0) == ':'
        else if (i < expression.length)
            root.right = convertExpression(expression, i+1);
       
        return root;
    }
      
    // function print tree
    public void printTree( Node root)
    {
        if (root == null)
            return;
                  
        System.out.print(root.data +" ");
        printTree(root.left);
        printTree(root.right);
    }
      
// Driver program to test above function
    public static void main(String args[]) 
    {
        String exp = "a?b?c:d:e";
        BinaryTree tree = new BinaryTree();
        char[] expression=exp.toCharArray(); 
        Node root = tree.convertExpression(expression, 0);
        tree.printTree(root) ;
    }
}
  
/* This code is contributed by Mr. Somesh Awasthi */

Python3

# Class to define a node 
# structure of the tree
class Node:
    def __init__(self, key):
        self.data = key
        self.left = None
        self.right = None
  
# Function to convert ternary 
# expression to a Binary tree
# It returns the root node 
# of the tree
def convert_expression(expression, i):
    if i >= len(expression):
        return None
  
    # Create a new node object
    # for the expression at
    # ith index
    root = Node(expression[i])
  
    i += 1
  
    # if current character of 
    # ternary expression is '?'
    # then we add next character 
    # as a left child of
    # current node
    if (i < len(expression) and 
                expression[i] is "?"):
        root.left = convert_expression(expression, i + 1)
          
    # else we have to add it 
    # as a right child of
    # current node expression[0] == ':'
    elif i < len(expression):
        root.right = convert_expression(expression, i + 1)
    return root
  
# Function to print the tree
# in a pre-order traversal pattern
def print_tree(root):
    if not root:
        return
    print(root.data, end=' ')
    print_tree(root.left)
    print_tree(root.right)
  
# Driver Code
if __name__ == "__main__":
    string_expression = "a?b?c:d:e"
    root_node = convert_expression(string_expression, 0)
    print_tree(root_node)
  
# This code is contributed
# by Kanav Malhotra

C#

// C# program to covert a ternary 
// expreesion to a tree. 
using System;
  
// Class to represent Tree node 
public class Node
{
    public char data;
    public Node left, right;
  
    public Node(char item)
    {
        data = item;
        left = null;
        right = null;
    }
}
  
// Class to covert a ternary 
// expression to a Tree 
public class BinaryTree
{
    // Function to convert Ternary Expression 
    // to a Binary Tree. It return the root of tree 
    public virtual Node convertExpression(char[] expression,
                                          int i)
    {
        // Base case 
        if (i >= expression.Length)
        {
            return null;
        }
  
        // store current character of 
        // expression_string [ 'a' to 'z'] 
        Node root = new Node(expression[i]);
  
        // Move ahead in str 
        ++i;
  
        // if current character of ternary expression 
        // is '?' then we add next character as a 
        // left child of current node 
        if (i < expression.Length && expression[i] == '?')
        {
            root.left = convertExpression(expression, i + 1);
        }
  
        // else we have to add it as a right child 
        // of current node expression.at(0) == ':' 
        else if (i < expression.Length)
        {
            root.right = convertExpression(expression, i + 1);
        }
  
        return root;
    }
  
    // function print tree 
    public virtual void printTree(Node root)
    {
        if (root == null)
        {
            return;
        }
  
        Console.Write(root.data + " ");
        printTree(root.left);
        printTree(root.right);
    }
  
// Driver Code
public static void Main(string[] args)
{
    string exp = "a?b?c:d:e";
    BinaryTree tree = new BinaryTree();
    char[] expression = exp.ToCharArray();
    Node root = tree.convertExpression(expression, 0);
    tree.printTree(root);
}
}
  
// This code is contributed by Shrikant13


Output :

a b c d e 


Time Complexity :
O(n) [ here n is length of String ]

Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.



This article is attributed to GeeksforGeeks.org

leave a comment

code

0 Comments

load comments

Subscribe to Our Newsletter