Print characters and their frequencies in order of occurrence using Binary Tree

0 0 11 minutes read

Given a string str containing only lowercase characters. The problem is to print the characters along with their frequency in the order of their occurrence using Binary Tree
Examples:

Input: str = “aaaabbnnccccz”
Output: “a4b2n2c4z”
Explanation:

Input: str = “zambiatek”
Output: g2e4k2s2for

Approach:

Start with the first character in the string.
Perform a level order insertion of the character in the Binary Tree
Pick the next character:
- If the character has been seen and we encounter it during level order insertion increase the count of the node.
- If the character has not been seen so far, go to step number 2.
Repeat the process for all the characters of the string.
Print the level order traversal of the tree which should output the desired output.

Below is the implementation of the above approach:

C++

// C++ implementation of
// the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Node in the tree where
// data holds the character
// of the string and cnt
// holds the frequency
struct node {
    char data;
    int cnt;
    node *left, *right;
};
 
// Function to add a new
// node to the Binary Tree
node* add(char data)
{
 
    // Create a new node and
    // populate its data part,
    // set cnt as 1 and left
    // and right children as NULL
    node* newnode = new node;
    newnode->data = data;
    newnode->cnt = 1;
    newnode->left = newnode->right = NULL;
 
    return newnode;
}
 
// Function to add a node
// to the Binary Tree in
// level order
node* addinlvlorder(node* root, char data)
{
 
    if (root == NULL) {
        return add(data);
    }
    // Use the queue data structure
    // for level order insertion
    // and push the root of tree to Queue
    queue<node*> Q;
    Q.push(root);
 
    while (!Q.empty()) {
 
        node* temp = Q.front();
        Q.pop();
 
        // If the character to be
        // inserted is present,
        // update the cnt
        if (temp->data == data) {
            temp->cnt++;
            break;
        }
        // If the left child is
        // empty add a new node
        // as the left child
        if (temp->left == NULL) {
            temp->left = add(data);
            break;
        }
        else {
            // If the character is present
            // as a left child, update the
            // cnt and exit the loop
            if (temp->left->data == data) {
                temp->left->cnt++;
                break;
            }
            // Add the left child to
            // the queue for further
            // processing
            Q.push(temp->left);
        }
        // If the right child is empty,
        // add a new node to the right
        if (temp->right == NULL) {
            temp->right = add(data);
            break;
        }
        else {
            // If the character is present
            // as a right child, update the
            // cnt and exit the loop
            if (temp->right->data == data) {
                temp->right->cnt++;
                break;
            }
            // Add the right child to
            // the queue for further
            // processing
            Q.push(temp->right);
        }
    }
 
    return root;
}
 
// Function to print the
// level order traversal of
// the Binary Tree
void printlvlorder(node* root)
{
 
    // Add the root to the queue
    queue<node*> Q;
    Q.push(root);
 
    while (!Q.empty()) {
        node* temp = Q.front();
        // If the cnt of the character
        // is more than one, display cnt
        if (temp->cnt > 1) {
            cout << temp->data << temp->cnt;
        }
        // If the cnt of character
        // is one, display character only
        else {
            cout << temp->data;
        }
        Q.pop();
        // Add the left child to
        // the queue for further
        // processing
        if (temp->left != NULL) {
            Q.push(temp->left);
        }
        // Add the right child to
        // the queue for further
        // processing
        if (temp->right != NULL) {
            Q.push(temp->right);
        }
    }
}
 
// Driver code
int main()
{
 
    string s = "zambiatek";
    node* root = NULL;
 
    // Add individual characters
    // to the string one by one
    // in level order
    for (int i = 0; i < s.size(); i++) {
        root = addinlvlorder(root, s[i]);
    }
 
    // Print the level order
    // of the constructed
    // binary tree
    printlvlorder(root);
 
    return 0;
}

Java

// Java implementation of
// the above approach
import java.util.*;
 
class GFG
{
 
// Node in the tree where
// data holds the character
// of the String and cnt
// holds the frequency
static class node
{
    char data;
    int cnt;
    node left, right;
};
 
// Function to add a new
// node to the Binary Tree
static node add(char data)
{
 
    // Create a new node and
    // populate its data part,
    // set cnt as 1 and left
    // and right children as null
    node newnode = new node();
    newnode.data = data;
    newnode.cnt = 1;
    newnode.left = newnode.right = null;
 
    return newnode;
}
 
// Function to add a node
// to the Binary Tree in
// level order
static node addinlvlorder(node root, char data)
{
 
    if (root == null) 
    {
        return add(data);
    }
     
    // Use the queue data structure
    // for level order insertion
    // and push the root of tree to Queue
    Queue<node> Q = new LinkedList<node>();
    Q.add(root);
 
    while (!Q.isEmpty())
    {
 
        node temp = Q.peek();
        Q.remove();
 
        // If the character to be
        // inserted is present,
        // update the cnt
        if (temp.data == data)
        {
            temp.cnt++;
            break;
        }
         
        // If the left child is
        // empty add a new node
        // as the left child
        if (temp.left == null)
        {
            temp.left = add(data);
            break;
        }
        else
        {
            // If the character is present
            // as a left child, update the
            // cnt and exit the loop
            if (temp.left.data == data)
            {
                temp.left.cnt++;
                break;
            }
             
            // Add the left child to
            // the queue for further
            // processing
            Q.add(temp.left);
        }
         
        // If the right child is empty,
        // add a new node to the right
        if (temp.right == null) 
        {
            temp.right = add(data);
            break;
        }
        else
        {
            // If the character is present
            // as a right child, update the
            // cnt and exit the loop
            if (temp.right.data == data)
            {
                temp.right.cnt++;
                break;
            }
             
            // Add the right child to
            // the queue for further
            // processing
            Q.add(temp.right);
        }
    }
 
    return root;
}
 
// Function to print the
// level order traversal of
// the Binary Tree
static void printlvlorder(node root)
{
 
    // Add the root to the queue
    Queue<node> Q = new LinkedList<node>();
    Q.add(root);
 
    while (!Q.isEmpty())
    {
        node temp = Q.peek();
         
        // If the cnt of the character
        // is more than one, display cnt
        if (temp.cnt > 1)
        {
            System.out.print((temp.data +""+ temp.cnt));
        }
         
        // If the cnt of character
        // is one, display character only
        else
        {
            System.out.print((char)temp.data);
        }
        Q.remove();
         
        // Add the left child to
        // the queue for further
        // processing
        if (temp.left != null) 
        {
            Q.add(temp.left);
        }
         
        // Add the right child to
        // the queue for further
        // processing
        if (temp.right != null)
        {
            Q.add(temp.right);
        }
    }
}
 
// Driver code
public static void main(String[] args)
{
 
    String s = "zambiatek";
    node root = null;
 
    // Add individual characters
    // to the String one by one
    // in level order
    for (int i = 0; i < s.length(); i++)
    {
        root = addinlvlorder(root, s.charAt(i));
    }
 
    // Print the level order
    // of the constructed
    // binary tree
    printlvlorder(root);
 
}
}
 
// This code is contributed by Rajput-Ji

Python3

# Python implementation of
# the above approach
 
# Node in the tree where
# data holds the character
# of the String and cnt
# holds the frequency
class node:
    def __init__(self):
        self.data = ''
        self.cnt = 0
        self.left = None
        self.right = None
 
# Function to add a new
# node to the Binary Tree
def add(data):
 
    # Create a new node and
    # populate its data part,
    # set cnt as 1 and left
    # and right children as None
    newnode = node()
    newnode.data = data
    newnode.cnt = 1
    newnode.left = newnode.right = None
 
    return newnode
 
# Function to add a node
# to the Binary Tree in
# level order
def addinlvlorder(root, data):
 
    if (root == None): 
        return add(data)
     
    # Use the queue data structure
    # for level order insertion
    # and push the root of tree to Queue
    Q = []
    Q.append(root)
 
    while (len(Q) != 0):
 
        temp = Q[0]
        Q = Q[1:]
 
        # If the character to be
        # inserted is present,
        # update the cnt
        if (temp.data == data):
            temp.cnt += 1
            break
         
        # If the left child is
        # empty add a new node
        # as the left child
        if (temp.left == None):
            temp.left = add(data)
            break
        else:
            # If the character is present
            # as a left child, update the
            # cnt and exit the loop
            if (temp.left.data == data):
                temp.left.cnt += 1
                break
             
            # push the left child to
            # the queue for further
            # processing
            Q.append(temp.left)
         
        # If the right child is empty,
        # add a new node to the right
        if (temp.right == None): 
            temp.right = add(data)
            break
        else:
            # If the character is present
            # as a right child, update the
            # cnt and exit the loop
            if (temp.right.data == data):
                temp.right.cnt += 1
                break
             
            # push the right child to
            # the queue for further
            # processing
            Q.append(temp.right)
 
    return root
 
# Function to print the
# level order traversal of
# the Binary Tree
def printlvlorder(root):
 
    # push the root to the queue
    Q = []
    Q.append(root)
 
    while (len(Q) != 0):
        temp = Q[0]
 
        # If the cnt of the character
        # is more than one, display cnt
        if (temp.cnt > 1):
            print(f"{temp.data}{temp.cnt}",end="")
         
        # If the cnt of character
        # is one, display character only
        else:
            print(temp.data,end="")
        Q = Q[1:]
         
        # push the left child to
        # the queue for further
        # processing
        if (temp.left != None): 
            Q.append(temp.left)
         
        # push the right child to
        # the queue for further
        # processing
        if (temp.right != None):
            Q.append(temp.right)
 
# Driver code
s = "zambiatek"
root = None
 
# push individual characters
# to the String one by one
# in level order
for i in range(len(s)):
    root = addinlvlorder(root, s[i])
     
# Print the level order
# of the constructed
# binary tree
printlvlorder(root)
 
# This code is contributed by shinjanpatra

C#

// C# implementation of
// the above approach
using System;
using System.Collections.Generic;
 
class GFG
{
 
// Node in the tree where
// data holds the character
// of the String and cnt
// holds the frequency
public class node
{
    public char data;
    public int cnt;
    public node left, right;
};
 
// Function to add a new
// node to the Binary Tree
static node add(char data)
{
 
    // Create a new node and
    // populate its data part,
    // set cnt as 1 and left
    // and right children as null
    node newnode = new node();
    newnode.data = data;
    newnode.cnt = 1;
    newnode.left = newnode.right = null;
 
    return newnode;
}
 
// Function to add a node
// to the Binary Tree in
// level order
static node addinlvlorder(node root, char data)
{
 
    if (root == null) 
    {
        return add(data);
    }
     
    // Use the queue data structure
    // for level order insertion
    // and push the root of tree to Queue
    List<node> Q = new List<node>();
    Q.Add(root);
 
    while (Q.Count != 0)
    {
 
        node temp = Q[0];
        Q.RemoveAt(0);
 
        // If the character to be
        // inserted is present,
        // update the cnt
        if (temp.data == data)
        {
            temp.cnt++;
            break;
        }
         
        // If the left child is
        // empty add a new node
        // as the left child
        if (temp.left == null)
        {
            temp.left = add(data);
            break;
        }
        else
        {
            // If the character is present
            // as a left child, update the
            // cnt and exit the loop
            if (temp.left.data == data)
            {
                temp.left.cnt++;
                break;
            }
             
            // Add the left child to
            // the queue for further
            // processing
            Q.Add(temp.left);
        }
         
        // If the right child is empty,
        // add a new node to the right
        if (temp.right == null) 
        {
            temp.right = add(data);
            break;
        }
        else
        {
            // If the character is present
            // as a right child, update the
            // cnt and exit the loop
            if (temp.right.data == data)
            {
                temp.right.cnt++;
                break;
            }
             
            // Add the right child to
            // the queue for further
            // processing
            Q.Add(temp.right);
        }
    }
 
    return root;
}
 
// Function to print the
// level order traversal of
// the Binary Tree
static void printlvlorder(node root)
{
 
    // Add the root to the queue
    List<node> Q = new List<node>();
    Q.Add(root);
 
    while (Q.Count != 0)
    {
        node temp = Q[0];
         
        // If the cnt of the character
        // is more than one, display cnt
        if (temp.cnt > 1)
        {
            Console.Write((temp.data +""+ temp.cnt));
        }
         
        // If the cnt of character
        // is one, display character only
        else
        {
            Console.Write((char)temp.data);
        }
        Q.RemoveAt(0);
         
        // Add the left child to
        // the queue for further
        // processing
        if (temp.left != null) 
        {
            Q.Add(temp.left);
        }
         
        // Add the right child to
        // the queue for further
        // processing
        if (temp.right != null)
        {
            Q.Add(temp.right);
        }
    }
}
 
// Driver code
public static void Main(String[] args)
{
 
    String s = "zambiatek";
    node root = null;
 
    // Add individual characters
    // to the String one by one
    // in level order
    for (int i = 0; i < s.Length; i++)
    {
        root = addinlvlorder(root, s[i]);
    }
 
    // Print the level order
    // of the constructed
    // binary tree
    printlvlorder(root);
 
}
}
 
// This code is contributed by Rajput-Ji

Javascript

<script>
  
// JavaScript implementation of
// the above approach
 
// Node in the tree where
// data holds the character
// of the String and cnt
// holds the frequency
class node
{
    constructor()
    {
        this.data = '';
        this.cnt = 0;
        this.left = null;
        this.right = null;
    }
};
 
// Function to add a new
// node to the Binary Tree
function add(data)
{
 
    // Create a new node and
    // populate its data part,
    // set cnt as 1 and left
    // and right children as null
    var newnode = new node();
    newnode.data = data;
    newnode.cnt = 1;
    newnode.left = newnode.right = null;
 
    return newnode;
}
 
// Function to add a node
// to the Binary Tree in
// level order
function addinlvlorder(root, data)
{
 
    if (root == null) 
    {
        return add(data);
    }
     
    // Use the queue data structure
    // for level order insertion
    // and push the root of tree to Queue
    var Q = [];
    Q.push(root);
 
    while (Q.length != 0)
    {
 
        var temp = Q[0];
        Q.shift();
 
        // If the character to be
        // inserted is present,
        // update the cnt
        if (temp.data == data)
        {
            temp.cnt++;
            break;
        }
         
        // If the left child is
        // empty add a new node
        // as the left child
        if (temp.left == null)
        {
            temp.left = add(data);
            break;
        }
        else
        {
            // If the character is present
            // as a left child, update the
            // cnt and exit the loop
            if (temp.left.data == data)
            {
                temp.left.cnt++;
                break;
            }
             
            // push the left child to
            // the queue for further
            // processing
            Q.push(temp.left);
        }
         
        // If the right child is empty,
        // add a new node to the right
        if (temp.right == null) 
        {
            temp.right = add(data);
            break;
        }
        else
        {
            // If the character is present
            // as a right child, update the
            // cnt and exit the loop
            if (temp.right.data == data)
            {
                temp.right.cnt++;
                break;
            }
             
            // push the right child to
            // the queue for further
            // processing
            Q.push(temp.right);
        }
    }
 
    return root;
}
 
// Function to print the
// level order traversal of
// the Binary Tree
function printlvlorder(root)
{
 
    // push the root to the queue
    var Q = [];
    Q.push(root);
 
    while (Q.length != 0)
    {
        var temp = Q[0];
         
        // If the cnt of the character
        // is more than one, display cnt
        if (temp.cnt > 1)
        {
            document.write((temp.data +""+ temp.cnt));
        }
         
        // If the cnt of character
        // is one, display character only
        else
        {
            document.write(temp.data);
        }
        Q.shift();
         
        // push the left child to
        // the queue for further
        // processing
        if (temp.left != null) 
        {
            Q.push(temp.left);
        }
         
        // push the right child to
        // the queue for further
        // processing
        if (temp.right != null)
        {
            Q.push(temp.right);
        }
    }
}
 
// Driver code
var s = "zambiatek";
var root = null;
// push individual characters
// to the String one by one
// in level order
for(var i = 0; i < s.length; i++)
{
    root = addinlvlorder(root, s[i]);
}
// Print the level order
// of the constructed
// binary tree
printlvlorder(root);
 
 
</script>

Output:

g2e4k2s2for

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!