<assignment 12><draft>

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

// The following is a employee in the organisation, it has the pointer to two more employees a subordinate_1 and a subordinate_2
struct Employee {
    int emp_id; // emp_ids will be unique
    char* emp_name;
    int emp_salary;
    struct Employee* subordinate_1;
    struct Employee* subordinate_2;
};

// The following function creates a employee and returns its pointer
struct Employee* create_employee(int id, char* name, int salary) {
    struct Employee* ptr = (struct Employee*) malloc(sizeof(struct Employee));
    ptr->emp_id = id;
    ptr->emp_salary = salary;
    ptr->emp_name = strdup(name);
    // strdup() creates a copy of the string or char pointer and stores it in the new char pointer of the employee
    ptr->subordinate_1 = NULL;
    ptr->subordinate_2 = NULL;
    return ptr;
}

// The following code creates a organisation from scanning the input file
struct Employee* create_company() {
    int id, salary;
    char name[100];
    scanf("%d", &id);
    if(id == -1) return NULL; // -1 is used when there is a NULL pointer ie when no value is present

    scanf("%s %d", name, &salary);
    struct Employee* par = create_employee(id, name, salary);

    par->subordinate_1 = create_company();
    par->subordinate_2 = create_company();
    
    return par;
}

// The following function 
void print_company_helper(struct Employee* ceo) {
    // take input
    if(!ceo) {
        printf("%d ", -1);
        return;
    }
    printf("%d %s %d ", ceo->emp_id, ceo->emp_name, ceo->emp_salary);
    print_company_helper(ceo->subordinate_1);
    print_company_helper(ceo->subordinate_2);
    return;
}

void print_company(struct Employee* ceo) {
    print_company_helper(ceo);
    printf("\n");
    return;
} 

// --------------------------------------------------- YOU CAN EDIT BELOW THIS LINE -----------------------------------

struct Employee* CEO = NULL;
// CEO is a global pointer that points to the CEO of the company
int head(struct Employee* CEO, int val)
{
    int left = CEO->subordinate_1->emp_id;
    int right = CEO -> subordinate_2->emp_id;
    
    if ( CEO == NULL || CEO->emp_id==val){
        return -1;
    }
    // If current node is the required node
    else if ((left != NULL && left==val) || (right !=NULL && right==val)) {
        return CEO->emp_id;
    }
 
    else if(head(CEO->subordinate_1, val)!=NULL){
        return head(CEO->subordinate_1, val);
    }
    else if(head(CEO->subordinate_2, val)!=NULL){ 
        return head(CEO->subordinate_2, val);
    }
}
// The below function returns the employee id of the first common boss
int get_first_common_boss(int emp_id1,int emp_id2){
    if(emp_id1==CEO->emp_id || emp_id2==CEO->emp_id){
        return CEO->emp_id;
    }
    else if(emp_id1==head(CEO,emp_id2)){
        return head(CEO,emp_id2);
    }
    else if(emp_id2==head(CEO,emp_id1)){
        return head(CEO,emp_id1);
    }
    else if(head(CEO,emp_id1)==head(CEO,emp_id2)){
        return head(CEO,emp_id1);
    }
    else if(head(CEO,emp_id1)!=head(CEO,emp_id2)){
        emp_id1=head(CEO,emp_id1);
        emp_id2=head(CEO,emp_id2);
        return get_first_common_boss(emp_id1,emp_id2);
    }
    return 0;
}

//Print the employees with the same last name sperated by a space in the order of their level
void same_last_names(int emp_id){
    return;
}

// Print the bosses of the given employee in the order from CEO to immediate boss
void get_all_bosses(int emp_id){
    return;
}

// Return the average salary of the team with the given employee as head
double get_average_salary(int emp_id){
    return 0.0;
}
// --------------------------------------------------- YOU CAN EDIT ABOVE THIS LINE -----------------------------------

/* The following driver code creates a organisation for you and based on the input file
it will call all the functions that are necessary, your job is to edit the functions
above the line. Their descriptions are in the pdf and in the comments in the code. */

int main(int argc, char const *argv[])
{
    CEO = create_company();
    print_company(CEO);

    int T; 
    scanf("%d", &T);

    char operation_type[100];

    while(T--) {
        scanf("%s", operation_type);

        if(strcmp(operation_type, "get_first_common_boss") == 0) {
            int x,y;
            scanf("%d %d", &x, &y);
            int ans = get_first_common_boss(x,y);
            printf("%d\n", ans);
        } 
        else if(strcmp(operation_type, "same_last_names") == 0) {
            int x;
            scanf("%d", &x);
            same_last_names(x);
            printf("\n");
        } 
        else if(strcmp(operation_type, "get_all_bosses") == 0) {
            int x;
            scanf("%d", &x);
            get_all_bosses(x);
            printf("\n");
        } 
        else if(strcmp(operation_type, "get_average_salary") == 0) {
            int x;
            scanf("%d", &x);
            double ans = get_average_salary(x);
            printf("%.2f\n", ans);
        } 

    }

    return 0;
}