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
    struct Employee* subordinate_1;
    struct Employee* subordinate_2;
};
 
// The following function creates a employee and returns its pointer
struct Employee* create_employee(int x) {
    struct Employee* ptr = (struct Employee*) malloc(sizeof(struct Employee));
    ptr->emp_id = x;
    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 x;
    scanf("%d", &x);
 
    if(x == -1) return NULL; // -1 is used when there is a NULL pointer ie when no value is present
    struct Employee* par = create_employee(x);
 
    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 ", ceo->emp_id);
    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
 
 
/*  In this function you have to print all the employees at a given level, Note that ceo is at level 0
In any of the functions which involve printing you need not print -1 for NULL pointers */
 
 void printNodesAtLevel(struct Employee* CEO, int currentLevel, int level) {
   
  if(CEO == NULL) {
      return;   
  }  
  if(currentLevel == level) {
     printf("%d ", CEO->emp_id);
     return;
  }
              
  printNodesAtLevel(CEO->subordinate_1, currentLevel+1, level);
  printNodesAtLevel(CEO->subordinate_2, currentLevel+1, level);
}
 
void EmployeesAtSameLevel(int level) {
    // The level may be any integer
    printNodesAtLevel(CEO,0,level);
    return;
}
 
// You have to print the employees as you search the organization look for the examples in the pdf and the input.txt and output.txt for details
// Note: You do not have to print -1 for NULL pointers
 
void print_my_helper(struct Employee* ceo){
    if(ceo){
        printf("%d ", ceo->emp_id);
    }else{
        return;
    }
    print_my_helper(ceo->subordinate_1);
    print_my_helper(ceo->subordinate_2);
    return;
}
 
void get_employees() {
    struct Employee* ptr=CEO;
    print_my_helper(ptr);
    return;
}
 
/* In the following function you have to print the immediate team of a employee - it includes their boss and their subordinates
Note: You do not have to print -1 for NULL pointers */
// struct Employee*node=0;
// int left = node->subordinate_1->emp_id;
// int right = node -> subordinate_2->emp_id;
    
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);
    }
}

int team(struct Employee*CEO,int emp_id){
    // node->emp_id=emp_id;
    // node->emp_id=p;
    // int a = head(CEO,emp_id);
    // int left = node->subordinate_1->emp_id;
    // int right = node -> subordinate_2->emp_id;
    // printf("%d %d %d",a,left,right);
    int left = CEO -> subordinate_1->emp_id;
    int right = CEO -> subordinate_2->emp_id;
    
    // while (emp_id=CEO->emp_id){
    //     // if ( CEO == NULL){
    //     //     return;
    //     // }
    //     if(left==NULL && right==NULL){
    //         return head(CEO,emp_id);
    //     }
    //     else if(left!=NULL && right!=NULL){
    //         printf("%d %d %d ",head(CEO,emp_id),left,right);
    //     }
    //     else if(left==NULL){
    //         printf("%d %d ",head(CEO,emp_id),right);
    //     }
    //     else{
    //         printf("%d %d ",head(CEO,emp_id),left);
    //     }
    // }
    
    if(CEO=NULL)
        return 0;
    
    if(CEO->emp_id=emp_id)
        printf("%d %d ",left,right);
    
    
    int r=team(CEO->subordinate_1, emp_id);
    if(left=emp_id)
        return r;
    r=team(CEO->subordinate_2, emp_id);
        
    
    // while(emp_id!=CEO->emp_id){
        
    //     if(left=emp_id){
    //     return team(CEO->subordinate_1, emp_id);
    //     }
    //     else if(right=emp_id){ 
    //         return team(CEO->subordinate_2, emp_id);
    //     }
    //     else{
    //         return team(CEO->subordinate_1->subordinate_1,emp_id);
    //     }
    // }
}
 
void ImmediateTeam(int emp_id) {
    // struct Employee*node;
    // node->emp_id=emp_id;
    // team(CEO,emp_id);
    printf("%d %d ",head(CEO,emp_id),team(CEO,emp_id));
}
 
// The following function returns the level of a employee with the given emp_id

int getLevel(struct Employee* CEO, int emp_id, int level)
{
    if (CEO == NULL)
        return 0;
 
    if (CEO->emp_id == emp_id)
        return level;
 
    int downlevel = getLevel(CEO->subordinate_1, emp_id, level + 1);
    if (downlevel != 0)
        return downlevel;
 
    downlevel = getLevel(CEO->subordinate_2, emp_id, level + 1);
    return downlevel;
}

int Level(int emp_id) {
    // Note that ceo has level 0
    return getLevel(CEO,emp_id,0);
}
 
// The following function gives the distance between employees with emp_id1 and emp_id2
 
int max(int x, int y){
    if(x > y){
        return x;
    }else{
        return y;
    }
}
 
int ans;
 
int findDistance(struct Employee* CEO, int n1, int n2)
{
    if (!CEO) return 0;
    int left = findDistance(CEO->subordinate_1, n1, n2);
    int right = findDistance(CEO->subordinate_2, n1, n2);
      //if any node(n1 or n2) is found
    if (CEO->emp_id == n1 || CEO->emp_id == n2)
    {   
          //check if their is any descendant(n1 or n2)
          //if descendant exist then distance between descendant
          //and current root will be our answer.
        if (left || right)
        {
            ans = max(left, right);
            return 0;
        }
        else
            return 1;
    }
      //if current root is LCA of n1 and n2.
    else if (left && right)
    {   
        ans = left + right;
        return 0;
    }
      //if their is a descendant(n1 or n2).
    else if (left || right){
          //increment its distance
        return max(left, right) + 1;
    }
    //if neither n1 nor n2 exist as descendant.
    return 0;
}
 
int Distance(int emp_id1, int emp_id2) {
    // If emp_id1 and emp_id2 are equal the distance is 0, both emp_id's will exist in the organisation
    ans = 0;
    findDistance(CEO,emp_id1,emp_id2);
    return ans;
}
 
 
/* The following function takes an emp_id this will belong to a employee in the organisation and your task is to return the emp_id of its boss
Note: If the boss does not exit return -1 */



int Boss(int emp_id) {
    return head(CEO,emp_id); 
}
 
/* The following function returns the diameter of a Organisation - 
a diameter is the maximum distance between any two emp_ids in the organisation. You can use the distance function implemented above */
 
int height(struct Employee*CEO){
    if(CEO==NULL){
        return 0;
    }
    return max(height(CEO->subordinate_1),height(CEO->subordinate_2))+1;
}

int min(int x, int y){
    if(x > y){
        return y;
    }else{
        return x;
    }
}

int Diameter() {
    return height(CEO) + min(height(CEO->subordinate_1),height(CEO->subordinate_2))-1;
}
 
/* The following function takes an emp_id of a employee and returns the number of employees directly connected to it.
NULL pointers are not included */
 
int size(struct Employee*CEO,int emp_id,int q){
    // q=0;
    // while(head(CEO,emp_id)!=NULL){
        if(CEO=NULL){
            return q;
        }
        // else if(CEO->subordinate_1->NULL || CEO->subordinate_2->NULL){
        //     return 2;
        // }
        else if(CEO->emp_id==emp_id && CEO->subordinate_1!=NULL && CEO->subordinate_2!=NULL){
            return q+2;
        }
        else if(CEO->emp_id==emp_id && (CEO->subordinate_1!=NULL || CEO->subordinate_2!=NULL)){
            return q+1;
        }
        // else if(CEO->subordinate_1->emp_id==emp_id )
        int i=size(CEO->subordinate_1, emp_id,q);
        q=q+1;
        if(i!=0){
            return i;
        }
        i=size(CEO->subordinate_2, emp_id,q+1);
        return i;
}
 
int TeamSize(int emp_id) {
    return size(CEO,emp_id,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[20];
 
    while(T--) {
        scanf("%s", operation_type);
 
        if(strcmp(operation_type, "level") == 0) {
            int x;
            scanf("%d", &x);
            int d = Level(x);
            printf("%d\n", d);
        } 
 
        if(strcmp(operation_type, "distance") == 0) {
            int x, y;
            scanf("%d %d", &x, &y);
            int d = Distance(x, y);
            printf("%d\n", d);
        }
 
        if(strcmp(operation_type, "employees_at_same_level") == 0) {
            int x;
            scanf("%d", &x);
            EmployeesAtSameLevel(x);
            printf("\n");
        }
 
        if(strcmp(operation_type, "get_employees") == 0) {
            get_employees();
            printf("\n");
        }
 
        if(strcmp(operation_type, "boss") == 0) {
            int x;
            scanf("%d", &x);
            int d = Boss(x);
            printf("%d\n", d);
        }
 
        if(strcmp(operation_type, "diameter") == 0) {
            int d = Diameter();
            printf("%d\n", d);
        }
 
        if(strcmp(operation_type, "immediate_team") == 0) {
            int x;
            scanf("%d", &x);
            ImmediateTeam(x);
            printf("\n");
        }
 
        if(strcmp(operation_type, "team_size") == 0) {
            int x;
            scanf("%d", &x);
            int d = TeamSize(x);
            printf("%d\n", d);
        }
    }
 
    return 0;
}