/* 
* Binary Tree
* output 1)node_number, 2)parent_number, 3)depth, 4)kind_of_node, 5)child_list
*/

/* inclution */
#include <stdio.h>

/* Definition */
#define MAX 100000
#define NIL -1

/* Prototype */
void printTree(int);
void setDepth(int, int);
int setHeight(int);
int getSibling(int);
int getDegree(int);

/* Global Variables */
struct node {
  int parent, left, right;
};
typedef struct node Node;

Node T[MAX]; //array for tree
int n; //number of tree array
int D[MAX]; //array for depth
int H[MAX]; //array for hight

/* main */
int main(){
  int i,j,key,left,right,root=0;
  
  /* input the number of A[] */
  scanf("%d",&n);
  
  /* initialize array */
  for(i=0;i<n;i++) { //??¨??????NIL??§?????????
    T[i].parent = NIL;
    T[i].left = NIL;
    T[i].right = NIL;
  }
  
  /* input datas */
  for(i=0;i<n;i++){
    scanf("%d", &key);
    scanf("%d%d",&left, &right);
    //??????????´?
    T[key].left = left;
    T[key].right = right;

    //???????????¨????????????????????????????¨????
    if(left != NIL) {
      T[left].parent = key;
    }
    if(right != NIL) {
      T[right].parent = key;
    }
  }

  /* set root node */
  for(i=0;i<n;i++){
    if(T[i].parent == NIL) {
      root = i;
    }
  }

  //complete depth array
  setDepth(root, 0); //??????depth = 0
  
  //complete height array
  setHeight(root);

  /* print out */
  for(i=0;i<n;i++) {
    printTree(i); //print????????????
  }

  return 0;
}

/* Print ???????????? */
void printTree(int u) { //u???node??????
  int i, c;
  /* each elements */
  printf("node %d: ",u); //node
  printf("parent = %d, ", T[u].parent);
  printf("sibling = %d, ", getSibling(u));
  printf("degree = %d, ", getDegree(u));
  printf("depth = %d, ", D[u]);
  printf("height = %d, ", H[u]);
  
  /* kind of node */
  if(T[u].parent == NIL) { //root???????????????????????§
    printf("root");
  }else if(getDegree(u) == 0) { //????????????????????°
    printf("leaf");
  }else { //????????\?????????????????????
    printf("internal node");
  }
  printf("\n");
}


void setDepth(int u, int d){ //u: node??????
  if(u==NIL) return; //?????°?????????????????????NIL?????£????????????return

  D[u] = d; //depth???????´?
  if(T[u].left!=NIL) { //???????¢????
    setDepth(T[u].left, d+1); //depth????¢???????????????°
  }
  if(T[u].right!=NIL) { //???????¢????
    setDepth(T[u].right, d+1); //depth????¢???????????????°
  }
}

int setHeight(int u){ //u: node??????
  int l_height=0, r_height=0;

  if(T[u].left != NIL) { //???????¢????
    l_height = setHeight(T[u].left) + 1; //?????????????????¨????????¨???,height??????????¢????????????????????????????
  }
  if(T[u].right != NIL) { //???????¢????
    r_height = setHeight(T[u].right) + 1; //?????????????????¨????????¨???,height??????????¢????????????????????????????
  }
  //??§?????????????????¨
  if(l_height > r_height) {
    H[u] = l_height;
  }else {
    H[u] = r_height;
  }
  return H[u];
}

int getSibling(int u) {
  //????????¨????????????????????????????????????1???
  //???????????¨??????????????°?????????????????????????????????(????¶??????¬?????????...)
  if(T[u].parent == NIL) {
    return NIL;
  }
  //????????\???????????????left????????¨????????°
  if(T[T[u].parent].left != u && T[T[u].parent].left != NIL) {
    return T[T[u].parent].left;
  }
  //????????\???????????????right????????¨????????°
  if(T[T[u].parent].right != u && T[T[u].parent].right != NIL) {
    return T[T[u].parent].right;
  }
  //???????????§??°??????????????°??????????????????
  return NIL;
}

int getDegree(int u) {
  int cnt=0;
  if(T[u].left != NIL){
    cnt++;
  }
  if(T[u].right != NIL){
    cnt++;
  }
  return cnt;
}

Measured memory_bytes: 616