Convert ternary expression to Binary Tree using Stack - Coding

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 structure
struct Node {
    char data;
    Node *left, *right;
};
 
// Function to create a new node
Node* 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 tree
void preorder(Node* root)
{
    if (root == NULL)
        return;
    cout << root->data << " ";
    preorder(root->left);
    preorder(root->right);
}
 
// Function to convert the expression to a binary tree
Node* 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 code
int 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 approach
import 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 Structure
class 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 node
def createNewNode(data):
    node = Node(data)
    return node
 
# Function to print the preorder
# traversal of the tree
def preorder(root):
    if (root == None):
        return
    print(root.data, end = " ")
    preorder(root.left)
    preorder(root.right)
 
# Function to convert the expression to a binary tree
def 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 expression
root = convertExpression(Str)
 
# Print the preorder traversal
preorder(root)
 
# This code is contributed by divyeshrabadiya07.

C#

// C# implementation of the approach
using 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

Reffered: https://www.geeksforgeeks.org

C++

Related
ios manipulators oct() function in C++
ios manipulators left() function in C++
ios manipulators hex() function in C++
ios manipulators right() function in C++
OpenCV \| Understanding Contrast in an Image

Type:	Geek
Category:	Coding
Sub Category:	Tutorial
Uploaded by:	Admin
Views:	8