Convert Ternary Expression to a Binary Tree

Last Updated : 14 Sep, 2023

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 .

If we see Symbol ‘?’

then we add next character as the left child of root.

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 convert 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 convert a ternary  
// expression 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 convert 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 convert a ternary  
// expression 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 convert 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 

Javascript

<script> 
   
// Javascript program to convert a ternary  
// expreesion to a tree.  
  
// Class to represent Tree node  
class Node 
{ 
    constructor(item) 
    { 
        this.data = item; 
        this.left = null; 
        this.right = null; 
    } 
} 
  
// Function to convert Ternary Expression  
// to a Binary Tree. It return the root of tree  
function convertExpression(expression, i) 
{ 
      
    // Base case  
    if (i >= expression.length) 
    { 
        return null; 
    } 
      
    // Store current character of  
    // expression_string [ 'a' to 'z']  
    var 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  
function printTree(root) 
{ 
    if (root == null) 
    { 
        return; 
    } 
    document.write(root.data + " "); 
    printTree(root.left); 
    printTree(root.right); 
} 
  
// Driver code 
var exp = "a?b?c:d:e"; 
var expression = exp.split(''); 
var root = convertExpression(expression, 0); 
printTree(root); 
  
// This code is contributed by noob2000 
  
</script>

Output

a b c d e

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

Approach for Converting Ternary Expression to Binary Tree.

The algorithm uses a recursive approach to build the tree in a top-down manner.
It starts with creating a new node for the current character at the current index.
If the next character is a ‘?’, it means that the current node needs a left child. So, the algorithm calls itself recursively with the next index to create the left child of the current node.
If the next character is a ‘:’, it means that the current node needs a right child. So, the algorithm calls itself recursively with the next index to create the right child of the current node.
Finally, the algorithm returns the root node of the binary tree.

Here is the implementation of above approach:-

C++

#include <bits/stdc++.h> 
using namespace std; 
  
class Node { 
public: 
    char val; 
    Node *left, *right; 
    Node(char v) : val(v), left(nullptr), right(nullptr) {} 
}; 
  
Node* ternaryToTree(string exp) { 
    if (exp.empty()) return nullptr; 
    Node *root = new Node(exp[0]); 
    stack<Node*> st; 
    st.push(root); 
    for (int i = 1; i < exp.size(); i += 2) { 
        Node *cur = st.top(); st.pop(); 
        if (exp[i] == '?') { 
            cur->left = new Node(exp[i+1]); 
            st.push(cur); 
            st.push(cur->left); 
        } else { 
            cur->right = new Node(exp[i+1]); 
            st.push(cur->right); 
        } 
    } 
    return root; 
} 
  
void printTree(Node* root) { 
    if (!root) return; 
    cout << root->val << " "; 
    printTree(root->left); 
    printTree(root->right); 
} 
  
int main() { 
    string exp = "a?b?c:d:e"; 
    Node *root = ternaryToTree(exp); 
    printTree(root); 
    return 0; 
} 

Java

import java.util.*; 
  
class Node { 
    char val; 
    Node left, right; 
    public Node(char v) { val = v; } 
} 
  
class Solution { 
    public static Node ternaryToTree(String exp) { 
        if (exp == null || exp.length() == 0) return null; 
        Node root = new Node(exp.charAt(0)); 
        Stack<Node> st = new Stack<>(); 
        st.push(root); 
        for (int i = 1; i < exp.length(); i += 2) { 
            Node cur = st.pop(); 
            if (exp.charAt(i) == '?') { 
                cur.left = new Node(exp.charAt(i+1)); 
                st.push(cur); 
                st.push(cur.left); 
            } else { 
                cur.right = new Node(exp.charAt(i+1)); 
                st.push(cur.right); 
            } 
        } 
        return root; 
    } 
  
    public static void printTree(Node root) { 
        if (root == null) return; 
        System.out.print(root.val + " "); 
        printTree(root.left); 
        printTree(root.right); 
    } 
  
    public static void main(String[] args) { 
        String exp = "a?b?c:d:e"; 
        Node root = ternaryToTree(exp); 
        printTree(root); 
    } 
} 

Python3

class Node: 
    def __init__(self, val): 
        self.val = val 
        self.left = None
        self.right = None
  
def ternary_to_tree(exp): 
    if not exp: 
        return None
    root = Node(exp[0]) 
    stack = [root] 
    for i in range(1, len(exp)): 
        if exp[i] == '?': 
            stack[-1].left = Node(exp[i+1]) 
            stack.append(stack[-1].left) 
        elif exp[i] == ':': 
            stack.pop() 
            while stack[-1].right: 
                stack.pop() 
            stack[-1].right = Node(exp[i+1]) 
            stack.append(stack[-1].right) 
    return root 
  
def print_tree(root): 
    if not root: 
        return
    print(root.val, end=' ') 
    print_tree(root.left) 
    print_tree(root.right) 
  
if __name__ == "__main__": 
    exp = "a?b?c:d:e"
    root = ternary_to_tree(exp) 
    print_tree(root) 

C#

using System; 
using System.Collections.Generic; 
  
class Node{ 
    public char val; 
    public Node left, right; 
    public Node(char v) { val = v; } 
} 
  
class Solution{ 
    // Function to convert a ternary expression to a tree 
    public static Node ternaryToTree(string exp){ 
        if (exp == null || exp.Length == 0) return null; 
        Node root = new Node(exp[0]); // Create the root node 
        Stack<Node> st = new Stack<Node>(); // Stack to track nodes 
        st.Push(root); // Push root to the stack 
        for (int i = 1; i < exp.Length; i += 2){ 
            Node cur = st.Pop(); // Pop the top node from the stack 
            if (exp[i] == '?'){ 
                cur.left = new Node(exp[i + 1]); // Create a left child node 
                st.Push(cur); // Push the current node back to the stack 
                st.Push(cur.left); // Push the left child node to the stack 
            } 
            else{ 
                cur.right = new Node(exp[i + 1]); // Create a right child node 
                st.Push(cur.right); // Push the right child node to the stack 
            } 
        } 
        return root; // Return the root node of the tree 
    } 
  
    // Function to print the tree in pre-order traversal 
    public static void printTree(Node root){ 
        if (root == null) return; 
        Console.Write(root.val + " "); // Print the current node 
        printTree(root.left); // Recursively print the left subtree 
        printTree(root.right); // Recursively print the right subtree 
    } 
  
    public static void Main(string[] args){ 
        string exp = "a?b?c:d:e"; 
        Node root = ternaryToTree(exp); 
        printTree(root); 
    } 
} 
  
// THIS CODE IS CONTRIBUTED BY CHANDAN AGARWAL

Javascript

class Node { 
  constructor(val) { 
    this.val = val; 
    this.left = null; 
    this.right = null; 
  } 
} 
  
let i = 0; 
  
function convertExpression(expression) { 
  if (!expression || i >= expression.length) { 
    return null; 
  } 
  
  const root = new Node(expression[i]); 
  i++; 
  
  if (i < expression.length && expression[i] === "?") { 
    i++; 
    root.left = convertExpression(expression); 
  } 
  
  if (i < expression.length && expression[i] === ":") { 
    i++; 
    root.right = convertExpression(expression); 
  } 
  
  return root; 
} 
  
function printTree(root) { 
  if (!root) { 
    return; 
  } 
  
  console.log(root.val + " "); 
  printTree(root.left); 
  printTree(root.right); 
} 
  
const stringExpression = "a?b?c:d:e"; 
const rootNode = convertExpression(stringExpression); 
printTree(rootNode); 

Output

a b c d e

Time complexity: O(n) – Since we visit each character of the expression exactly once.

Space complexity: O(n) – Since in the worst case, the recursion stack can grow to the height of the tree, which can be O(n) if the ternary expression is a degenerate tree (a long chain of ‘?’). Additionally, we store O(n) nodes in the binary tree.

Nishant Singh

Improve

Convert a Binary Tree to a Circular Doubly Link List

Check if there is a root to leaf path with given sequence

Types of Binary Tree

Some important Binary tree traversals

Easy problems on Binary Tree

Intermediate problems on Binary Tree

Hard problems on Binary Tree

Convert Ternary Expression to a Binary Tree

C++

Java

Python3

C#

Javascript

Approach for Converting Ternary Expression to Binary Tree.

C++

Java

Python3

C#

Javascript

Please Login to comment...

Similar Reads

What kind of Experience do you want to share?