Huffman encoding for the word: CONNECTION

Step 1: Count frequency of each character

C O N N E C T I O N

Step 2: Build Huffman tree

One valid construction is:
E(1) + I(1) = 2
T(1) + C(2) = 3
O(2) + (E,I)(2) = 4
N(3) + (T,C)(3) = 6
4 + 6 = 10

Huffman tree:

                 [10]
                /    \
              [4]    [6]
             /  \    /  \
          O(2) [2] N(3) [3]
               / \       / \
            E(1) I(1) T(1) C(2)

Assign 0 to left branch and 1 to right branch

Encode CONNECTION

C = 111
O = 00
N = 10
N = 10
E = 010
C = 111
T = 110
I = 011
O = 00
N = 10

Encoded bit string:
1110010100101111100110010

#include <iostream>
using namespace std;
#define SIZE 100
int bst[SIZE];

// Initialize BST array
void initBST() {
    for(int i = 0; i < SIZE; i++)
        bst[i] = -1;
}

// Insert node in BST represented by array
int insertData(const int *arr, int x) {
    int index = 0;

    while(index < SIZE) {

        // If empty position found
        if(bst[index] == -1) {
            bst[index] = x;
            return index;
        }

        // Go to left child
        if(x < bst[index])
            index = 2 * index + 1;

        // Go to right child
        else
            index = 2 * index + 2;
    }

    return -1; // Tree full
}

int main() {
    initBST();

    insertData(bst, 50);
    insertData(bst, 30);
    insertData(bst, 70);
    insertData(bst, 20);
    insertData(bst, 40);

    cout << "BST array representation:\n";
    for(int i = 0; i < 15; i++) {
        if(bst[i] != -1)
            cout << "Index " << i << " : " << bst[i] << endl;
    }

    return 0;
}

Not fully Collected