Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
1.1.
Problem Statement
1.2.
Sample Examples
2.
Approach
2.1.
Pseudocode
2.2.
Implementation
2.2.1.
Complexity Analysis
3.
Frequently Asked Questions
3.1.
What are the features of BST?
3.2.
What does time complexity mean?
3.3.
What does space complexity mean?
3.4.
What are the limitations of the Binary search algorithm?
3.5.
List some types of binary trees.
4.
Conclusion
Last Updated: Mar 27, 2024
Medium

Convert Ternary Expression to a Binary Tree

Crack Google SDE interview : Essential projects
Speaker
Saurav Prateek
SDE-2 @
20 Jun, 2024 @ 01:30 PM

Introduction

This article will look at the problem of converting a given ternary expression into a binary tree. Binary tree questions are the most popular and vital in coding interviews and programming competitions. Let's understand the problem statement.

Convert Ternary Expression to Binary Tree

In computer science, a binary tree, by definition, is a tree data structure in which each node has at most 2 children, referred to as the left child and the right child.

Binary Tree Example

Binary Tree example

Problem Statement

We are given a string that contains ternary expressions. The expressions may be nested. Write a program to convert the given ternary expression to a binary Tree. 

Sample Examples

Example 1

Input 1: a?b:c
Output 1: a b c 
             a
           /   \
          b     c
Explanation: The preorder traversal of the above tree is a b c.

 

Example 2

Input 2: a?b?c:d:e
Output 2:  a b c d e
             a
           /   \
          b     e
         / \    
        c   d    
Explanation: The preorder traversal of the above tree is a b c d e.

Approach

Since the ternary operator has associativity from right to left, the string can be traversed from right to left. We will traverse a string, then make the first character as root and do the following step recursively. If we see Symbol '?', we add the next character as the left child of root, and if we see Symbol ':', then we add it as the right child of the current root. We will do this process until we traverse all elements of string.

Pseudocode

  • Create a function to convert Ternary Expression to a Binary Tree. It returns the root of the tree.
  • Write the base case that if the length of the string is exceeded we will return null.
  • Store current character of string as root node.
  • If current character of ternary expression is '?', then the next character is added as a left child of current node.
  • Else we add it as a right child of the current node.
  • Finally we will return root.

Implementation

Code in C++ 

#include <bits/stdc++.h>
using namespace std;

struct Node
{
    char data;
    Node *left, *right;
};

Node *newNode(char Data)
{
    Node *new_node = new Node;
    new_node->data = Data;
    new_node->left = new_node->right = NULL;
    return new_node;
}

// Function for converting Ternary Expression to a Binary Tree.
Node *convertExpression(string str, int &i)
{
    // to store current character of expression_string
    Node *root = newNode(str[i]);

    // Base Case
    if (i == str.length() - 1)
        return root;
    i++;
    if (str[i] == '?')
    {
        i++; // to skip the '?'
        // construct the left subtree
        root->left = convertExpression(str, i);
        i++; // skip the ':' character
        // construct the right subtree
        root->right = convertExpression(str, i);
        return root;
    }
    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;
}

 

Output:

a b c d e

Complexity Analysis

Time complexity: O(n); where n is the length of the expression.

Space Complexity: O(1)

Check out this problem - Diameter Of Binary Tree

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Frequently Asked Questions

What are the features of BST?

The 2 features of A binary search tree (BST) are: Each node has a maximum of two children. For each node, the values of its left child nodes are less than that of the present or current node, which in turn is less than the right child nodes (if any).

What does time complexity mean?

The time complexity in computer science is the computational complexity that describes how long it takes a computer to run an algorithm. Choosing the most efficient algorithm is always better when a fundamental problem can be solved using multiple methods.

What does space complexity mean?

The space complexity of an algorithm is the total space taken by the algorithm with respect to the input size. In simple words, An algorithm's amount of memory is known as its space complexity.

What are the limitations of the Binary search algorithm?

The limitations of the Binary Search Algorithm are: It uses a recursive approach which requires more stack space. Programming a binary search algorithm is difficult and error-prone. The interaction of this algorithm with memory hierarchy (caching) is poor.

List some types of binary trees.

Some types of Binary trees are

Full Binary Tree, Perfect Binary Tree, Complete Binary Tree, Degenerate or Pathological Tree, Skewed Binary Tree and Balanced Binary Tree.

Conclusion

This article discussed the solution for converting a given ternary expression to a binary tree along with its different approaches, pseudocode, implementation, and code in both Python and C++.

Refer to our Guided Path on Coding Ninjas Studio to upskill yourself in Data Structures and AlgorithmsCompetitive ProgrammingJavaScriptSystem DesignMachine learning and many more! If you want to test your competency in coding, you may check out the mock test series and participate in the contests hosted on Coding Ninjas Studio! But if you have just started your learning process and are looking for questions asked by tech giants like Amazon, Microsoft, Uber, etc; you must look at the problemsinterview experiences, and interview bundle for placement preparations.

Nevertheless, you may consider our paid courses to give your career an edge over others!

Do upvote our blogs if you find them helpful and engaging!

Happy Learning!!

Previous article
Converting Binary Tree to Binary Search Tree
Next article
Check whether the given Preorder, Inorder and Postorder traversals are of the same tree or not
Live masterclass