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 .
- 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> |
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); |
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.
Contact Us