/* 
 * File:   BinaryTree.cpp
 * Author: masa
 *
 * Created on 2016/03/04, 9:14
 */

#include <cstdlib>
#include <iostream>

#define MAX 26
#define NIL -1
using namespace std;

/*
 * 
 */

struct Node {
    int parent;
    int left;
    int right;
};

Node TreeNodeList[MAX];
int DepthList[MAX];
int HeightList[MAX];


void setDepth(int id, int depth) {
    DepthList[id] = depth;
    if(TreeNodeList[id].left != NIL) {
        setDepth(TreeNodeList[id].left, depth + 1);
    }
    
    if(TreeNodeList[id].right != NIL) {
        setDepth(TreeNodeList[id].right, depth + 1);
    }
}

int setHeight(int id) {
    //end-point
    if(TreeNodeList[id].left == NIL && TreeNodeList[id].right == NIL) {
        HeightList[id] = 0;
        return 0;
    }
    
    //decomposition-point
    int h1 = 0, h2 = 0;
    if(TreeNodeList[id].left != NIL) {
        h1 = setHeight(TreeNodeList[id].left) + 1;
    }
    if(TreeNodeList[id].right != NIL) {
        h2 = setHeight(TreeNodeList[id].right) + 1;
    }
    
    return HeightList[id] = (h1 > h2 ? h1 : h2);
}

void printTree(int id) {
    cout << "node " << id << ": " << "parent = " << TreeNodeList[id].parent << ", ";
    
    cout << "sibling = ";
    
    
    if(TreeNodeList[id].parent == NIL) {
        cout << "-1, ";
    }
    else if(TreeNodeList[TreeNodeList[id].parent].left != NIL && id != TreeNodeList[TreeNodeList[id].parent].right) {
        cout << TreeNodeList[TreeNodeList[id].parent].right << ", ";
    }
    else if(TreeNodeList[TreeNodeList[id].parent].right != NIL && id != TreeNodeList[TreeNodeList[id].parent].left){
        cout << TreeNodeList[TreeNodeList[id].parent].left << ", ";
    }
    else {
        cout << "-1, ";
    }
    
    
    int degree = 0;
    if(TreeNodeList[id].left != NIL) {
        degree++;
    }
    if(TreeNodeList[id].right != NIL) {
        degree++;
    }
    cout << "degree = " << degree << ", ";
    cout << "depth = " << DepthList[id] << ", ";
    cout << "height = " << HeightList[id] << ", ";
    
    if(TreeNodeList[id].parent == NIL) {
        cout << "root";
    }
    else if(TreeNodeList[id].left != NIL || TreeNodeList[id].right != NIL) {
        cout << "internal node";
    }
    else {
        cout << "leaf";
    }
    cout << endl;
}



int main(void) {
        
    int num;
    cin >> num;
    
    //all node is initialized to NIL
    for(int i = 0; i < num; i++) {
        TreeNodeList[i].parent = TreeNodeList[i].left = TreeNodeList[i].right = NIL;
    }
    
    int id, child;
    for(int i = 0; i < num; i++) {
        cin >> id;
        for(int j = 0; j < 2; j++) {
            cin >> child;
            if(j == 0) {
                TreeNodeList[id].left = child;
            }
            else {
                TreeNodeList[id].right = child;
            }
            if(child != NIL) {
                TreeNodeList[child].parent = id;
            }
        }
    }
    
    int rootId;
    for(int i = 0; i < num; i++) {
        if(TreeNodeList[i].parent == NIL) {
            rootId = i;
        }
    }
    
    setDepth(rootId, 0);
    setHeight(rootId);
    for(int i = 0; i < num; i++) {
        printTree(i);
    }
    
    return 0;
}

Measured memory_bytes: 1164