Huffman Coding using min priority queue

Question

In this Question, I need to print the huffman code for all the data. But for the given test case below, I'm getting different output.

Input

8

i j k l m n o p

5 9 12 13 16 45 55 70

Where

First line enters the number of letters

Second line enters the letters

Third line enters the frequencies of the letters

Expected Output

n: 00

k: 0100

l: 0101

i: 01100

j: 01101

m: 0111

o: 10

p: 11

My Output

n: 00

o: 01

k: 1000

l: 1001

i: 10100

j: 10101

m: 1011

p: 11

My code

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

struct Node {
    char data;
    int freq;
    Node *left, *right;
    Node(char x, int y): data(x), freq(y), left(NULL), right(NULL) {}
};

struct compare {
    bool operator()(Node *l, Node*r) {
        return l->freq > r->freq;
    }
};

void display(Node *p, string str) {
    if(p) {
        if(p->data != '$')
            cout << p->data << ": " << str << "\n";
        display(p->left, str + "0");
        display(p->right, str + "1");
    }
}

void huffmanCodes(char data[], int fr[], int n) {
    priority_queue<Node*, vector<Node*>, compare > pq;
    for(int i=0;i<n;i++)
        pq.push(new Node(data[i], fr[i]));
    while(pq.size() != 1) {
        Node *l = pq.top();
        pq.pop();
        Node *r = pq.top();
        pq.pop();
        Node *t = new Node('$', l->freq + r->freq);
        t->left = l;
        t->right = r; 
        pq.push(t);
    }
    display(pq.top(), "");
}

int main() {
    int n;
    cin >> n;
    char data[n];
    int freq[n];
    for(auto &x: data) cin >> x;
    for(auto &x: freq) cin >> x;
    huffmanCodes(data, freq, n);
}

Answer 1

Just to add to 500's correct answer, depending on the choice made, you can get either of these trees, both of which are valid and optimal:

By the way, since you also show bit assignments, for each of those two trees there are 128 ways to assign codes to the symbols. You can make each branch individually 0 on the left and 1 on the right, or 1 on the left and 0 on the right. So there are actually 256 different ways to make valid Huffman codes for those frequencies.