Counting Leaf Nodes in a Binary Tree

Calculate the number of leaf nodes within a binary tree. A leaf node is defined as a node where both the left and right child pointers are null.

#include <stdio.h>
#include <stdlib.h>

typedef char ElemType;
typedef struct BiTNode {
    ElemType data;
    struct BiTNode *lchild, *rchild;
} BiTNode, *BiTree;

BiTree Create(); /* Initialization omitted */

int countLeaves(BiTree root) {
    if (root == NULL) {
        return 0;
    }
    if (root->lchild == NULL && root->rchild == NULL) {
        return 1;
    }
    return countLeaves(root->lchild) + countLeaves(root->rchild);
}

int main() {
    BiTree root = Create();
    printf("%d\n", countLeaves(root));
    return 0;
}

Inserting into an Ascending Sorted Linked List

Insert a new integer value into an already sorted singly linked list that utilizes a dummy head node, ensuring the ascending order is preserved.

#include <stdio.h>
#include <stdlib.h>

typedef int ElementType;
typedef struct Node *PtrToNode;
struct Node {
    ElementType Data;
    PtrToNode   Next;
};
typedef PtrToNode List;

List Read(); /* Initialization omitted */
void Print(List L); /* Initialization omitted */

List insertSorted(List head, ElementType val) {
    List newNode = (List)malloc(sizeof(struct Node));
    newNode->Data = val;
    newNode->Next = NULL;
    
    List current = head;
    while (current->Next != NULL && current->Next->Data < val) {
        current = current->Next;
    }
    newNode->Next = current->Next;
    current->Next = newNode;
    return head;
}

int main() {
    List L;
    ElementType X;
    L = Read();
    scanf("%d", &X);
    L = insertSorted(L, X);
    Print(L);
    return 0;
}

Ranking Users by Unique Likes

Given a list of users and the items they liked, determine the top 3 users with the highest number of unique likes. If there is a tie in unique likes, the user with fewer total likes ranks higher. If the total number of users is less than 3, fill the missing positions with a dash "-".

Input example:

5
bob 11 101 102 103 104 105 106 107 108 108 107 107
peter 8 1 2 3 4 3 2 5 1
chris 12 1 2 3 4 5 6 7 8 9 1 2 3
john 10 8 7 6 5 4 3 2 1 7 5
jack 9 6 7 8 9 10 11 12 13 14

Output example:

jack chris john

#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
#include <string>

using namespace std;

struct User {
    string name;
    int totalClicks;
    int uniqueClicks;
};

bool compareUsers(const User& a, const User& b) {
    if (a.uniqueClicks != b.uniqueClicks) {
        return a.uniqueClicks > b.uniqueClicks;
    }
    return a.totalClicks < b.totalClicks;
}

int main() {
    int numUsers;
    cin >> numUsers;
    vector<User> users(numUsers);
    
    for (int i = 0; i < numUsers; ++i) {
        cin >> users[i].name;
        int clicks;
        cin >> clicks;
        users[i].totalClicks = clicks;
        
        set<int> uniqueItems;
        for (int j = 0; j < clicks; ++j) {
            int item;
            cin >> item;
            uniqueItems.insert(item);
        }
        users[i].uniqueClicks = uniqueItems.size();
    }
    
    sort(users.begin(), users.end(), compareUsers);
    
    for (int i = 0; i < 3; ++i) {
        if (i > 0) cout << " ";
        if (i < numUsers) {
            cout << users[i].name;
        } else {
            cout << "-";
        }
    }
    cout << endl;
    
    return 0;
}