Convert ternary expression to Binary Tree using Stack
Given a string str that contains a ternary expression which may be nested. The task is to convert the given ternary expression to a binary tree and return the root.
Examples:
Input: str = "a?b:c"
Output: a b c
a
/ \
b c
The preorder traversal of the above tree is a b c.
Input: str = "a?b?c:d:e"
Output: a b c d e
a
/ \
b e
/ \
c d
Approach: This is a stack-based approach to the given problem. Since the ternary operator has associativity from right-to-left, the string can be traversed from right to left. Take the letters one by one skipping the letters ‘?’ and ‘:’ as these letters are used to decide whether the current letter (alphabet [a to z]) will go into the stack or be used to pop the top 2 elements from the top of the stack to make them the children of the current letter which is then itself pushed into the stack. This forms the tree in a bottom-up manner and the last remaining element in the stack after the entire string is processed is the root of the tree.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;// Node structurestruct Node { char data; Node *left, *right;};// Function to create a new nodeNode* createNewNode(int data){ Node* node = new Node; node->data = data; node->left = NULL, node->right = NULL; return node;}// Function to print the preorder// traversal of the treevoid preorder(Node* root){ if (root == NULL) return; cout << root->data << " "; preorder(root->left); preorder(root->right);}// Function to convert the expression to a binary treeNode* convertExpression(string str){ stack<Node*> s; // If the letter is the last letter of // the string or is of the type :letter: or ?letter: // we push the node pointer containing // the letter to the stack for (int i = str.length() - 1; i >= 0;) { if ((i == str.length() - 1) || (i != 0 && ((str[i - 1] == ':' && str[i + 1] == ':') || (str[i - 1] == '?' && str[i + 1] == ':')))) { s.push(createNewNode(str[i])); } // If we do not push the current letter node to stack, // it means the top 2 nodes in the stack currently are the // left and the right children of the current node // So pop these elements and assign them as the // children of the current letter node and then // push this node into the stack else { Node* lnode = s.top(); s.pop(); Node* rnode = s.top(); s.pop(); Node* node = createNewNode(str[i]); node->left = lnode; node->right = rnode; s.push(node); } i -= 2; } // Finally, there will be only 1 element // in the stack which will be the // root of the binary tree return s.top();}// Driver codeint main(){ string str = "a?b?c:d:e"; // Convert expression Node* root = convertExpression(str); // Print the preorder traversal preorder(root); return 0;} |
Java
// Java implementation of the approachimport java.util.*;public class Main{ // Class containing left and // right child of current // node and key value static class Node { public char data; public Node left, right; public Node(char data) { this.data = data; left = right = null; } } // Function to create a new node static Node createNewNode(char data) { Node node = new Node(data); return node; } // Function to print the preorder // traversal of the tree static void preorder(Node root) { if (root == null) return; System.out.print(root.data + " "); preorder(root.left); preorder(root.right); } // Function to convert the expression to a binary tree static Node convertExpression(String str) { Stack<Node> s = new Stack<Node>(); // If the letter is the last letter of // the string or is of the type :letter: or ?letter: // we push the node pointer containing // the letter to the stack for (int i = str.length() - 1; i >= 0😉 { if ((i == str.length() - 1) || (i != 0 && ((str.charAt(i - 1) == ':' && str.charAt(i + 1) == ':') || (str.charAt(i - 1) == '?' && str.charAt(i + 1) == ':')))) { s.push(createNewNode(str.charAt(i))); } // If we do not push the current // letter node to stack, // it means the top 2 nodes in // the stack currently are the // left and the right children of the current node // So pop these elements and assign them as the // children of the current letter node and then // push this node into the stack else { Node lnode = (Node)s.peek(); s.pop(); Node rnode = (Node)s.peek(); s.pop(); Node node = createNewNode(str.charAt(i)); node.left = lnode; node.right = rnode; s.push(node); } i -= 2; } // Finally, there will be only 1 element // in the stack which will be the // root of the binary tree return (Node)s.peek(); } // Driver code public static void main(String[] args) { String str = "a?b?c:d:e"; // Convert expression Node root = convertExpression(str); // Print the preorder traversal preorder(root); }}// This code is contributed by divyesh072019. |
Python3
# Python3 implementation of the approach# Tree Structureclass Node: # Constructor to set the data of # the newly created tree node def __init__(self, data): self.data = data self.left = None self.right = None# Function to create a new nodedef createNewNode(data): node = Node(data) return node# Function to print the preorder# traversal of the treedef preorder(root): if (root == None): return print(root.data, end = " ") preorder(root.left) preorder(root.right)# Function to convert the expression to a binary treedef convertExpression(Str): s = [] # If the letter is the last letter of # the string or is of the type :letter: or ?letter: # we push the node pointer containing # the letter to the stack i = len(Str) - 1 while i >= 0: if ((i == len(Str) - 1) or (i != 0 and ((Str[i - 1] == ':' and Str[i + 1] == ':') or (Str[i - 1] == '?' and Str[i + 1] == ':')))): s.append(createNewNode(Str[i])) # If we do not push the current # letter node to stack, # it means the top 2 nodes in # the stack currently are the # left and the right children of the current node # So pop these elements and assign them as the # children of the current letter node and then # push this node into the stack else: lnode = s[-1] s.pop() rnode = s[-1] s.pop() node = createNewNode(Str[i]) node.left = lnode node.right = rnode s.append(node) i -= 2 # Finally, there will be only 1 element # in the stack which will be the # root of the binary tree return s[-1]Str = "a?b?c:d:e" # Convert expressionroot = convertExpression(Str)# Print the preorder traversalpreorder(root)# This code is contributed by divyeshrabadiya07. |
C#
// C# implementation of the approachusing System;using System.Collections;class GFG { // Class containing left and // right child of current // node and key value class Node { public char data; public Node left, right; public Node(char data) { this.data = data; left = right = null; } } // Function to create a new node static Node createNewNode(char data) { Node node = new Node(data); return node; } // Function to print the preorder // traversal of the tree static void preorder(Node root) { if (root == null) return; Console.Write(root.data + " "); preorder(root.left); preorder(root.right); } // Function to convert the expression to a binary tree static Node convertExpression(string str) { Stack s = new Stack(); // If the letter is the last letter of // the string or is of the type :letter: or ?letter: // we push the node pointer containing // the letter to the stack for (int i = str.Length - 1; i >= 0;) { if ((i == str.Length - 1) || (i != 0 && ((str[i - 1] == ':' && str[i + 1] == ':') || (str[i - 1] == '?' && str[i + 1] == ':')))) { s.Push(createNewNode(str[i])); } // If we do not push the current // letter node to stack, // it means the top 2 nodes in // the stack currently are the // left and the right children of the current node // So pop these elements and assign them as the // children of the current letter node and then // push this node into the stack else { Node lnode = (Node)s.Peek(); s.Pop(); Node rnode = (Node)s.Peek(); s.Pop(); Node node = createNewNode(str[i]); node.left = lnode; node.right = rnode; s.Push(node); } i -= 2; } // Finally, there will be only 1 element // in the stack which will be the // root of the binary tree return (Node)s.Peek(); } static void Main() { string str = "a?b?c:d:e"; // Convert expression Node root = convertExpression(str); // Print the preorder traversal preorder(root); }}// This code is contributed by decode2207. |
Javascript
<script> // JavaScript implementation of the approach class Node { constructor(data) { this.left = null; this.right = null; this.data = data; } } // Function to create a new node function createNewNode(data) { let node = new Node(data); return node; } // Function to print the preorder // traversal of the tree function preorder(root) { if (root == null) return; document.write(root.data + " "); preorder(root.left); preorder(root.right); } // Function to convert the expression to a binary tree function convertExpression(str) { let s = []; // If the letter is the last letter of // the string or is of the type :letter: or ?letter: // we push the node pointer containing // the letter to the stack for (let i = str.length - 1; i >= 0;) { if ((i == str.length - 1) || (i != 0 && ((str[i - 1] == ':' && str[i + 1] == ':') || (str[i - 1] == '?' && str[i + 1] == ':')))) { s.push(createNewNode(str[i])); } // If we do not push the current // letter node to stack, // it means the top 2 nodes in // the stack currently are the // left and the right children of the current node // So pop these elements and assign them as the // children of the current letter node and then // push this node into the stack else { let lnode = s[s.length - 1]; s.pop(); let rnode = s[s.length - 1]; s.pop(); let node = createNewNode(str[i]); node.left = lnode; node.right = rnode; s.push(node); } i -= 2; } // Finally, there will be only 1 element // in the stack which will be the // root of the binary tree return s[s.length - 1]; } let str = "a?b?c:d:e"; // Convert expression let root = convertExpression(str); // Print the preorder traversal preorder(root); </script> |
Output:
a b c d e
Time Complexity: O(n)
Auxiliary Space: O(n) because using stack s
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!
