Note

Algorithm

 

二分木

与えられた二分木 $T$ の各節点 $u$ について、以下の情報を出力するプログラムを作成してください。

• $u$ の節点番号
• $u$ の親
• $u$ の兄弟
• $u$ の子の数
• $u$ の深さ
• $u$ の高さ
• 節点の種類（根、内部節点または葉）

ここでは、与えられる二分木は $n$ 個の節点を持ち、それぞれ $0$ から $n − 1$ の番号が割り当てられているものとします。

入力

入力の最初の行に、節点の個数 $n$ が与えられます。続く $n$ 行目に、各節点の情報が以下の形式で１行に与えられます。

$id$ $left$ $right$

$id$ は節点の番号、$left$ は左の子の番号、$right$ は右の子の番号を表します。子を持たない場合は $left$ ($right$)は -1 で与えられます。

出力

次の形式で節点の情報を出力してください。

node $id$: parent = $p$, sibling = $s$, degree = $deg$, depth = $dep$, height = $h$, $type$

$p$ は親の番号を表します。親を持たない場合は -1 とします。$s$ は兄弟の番号を表します。兄弟を持たない場合は -1 とします。

$deg$、$dep$、$h$ はそれぞれ節点の子の数、深さ、高さを表します。

$type$ は根、内部節点、葉をそれぞれ表す root、internal node、leaf の文字列のいずれかです。ただし、根が葉や内部節点の条件に該当する場合は root とします。

出力例にて、空白区切り等の出力形式を確認してください。

制約

• $1 \leq n \leq 25$

入力例 1

9
0 1 4
1 2 3
2 -1 -1
3 -1 -1
4 5 8
5 6 7
6 -1 -1
7 -1 -1
8 -1 -1

出力例 1

node 0: parent = -1, sibling = -1, degree = 2, depth = 0, height = 3, root
node 1: parent = 0, sibling = 4, degree = 2, depth = 1, height = 1, internal node
node 2: parent = 1, sibling = 3, degree = 0, depth = 2, height = 0, leaf
node 3: parent = 1, sibling = 2, degree = 0, depth = 2, height = 0, leaf
node 4: parent = 0, sibling = 1, degree = 2, depth = 1, height = 2, internal node
node 5: parent = 4, sibling = 8, degree = 2, depth = 2, height = 1, internal node
node 6: parent = 5, sibling = 7, degree = 0, depth = 3, height = 0, leaf
node 7: parent = 5, sibling = 6, degree = 0, depth = 3, height = 0, leaf
node 8: parent = 4, sibling = 5, degree = 0, depth = 2, height = 0, leaf

参考文献

Introduction to Algorithms, Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. The MIT Press.

---