모든 잎(leaf)의 깊이가 같고, 모든 내부 노드의 차수(degree)가 k인(즉, 분기계수가 k인) 트리를 k진 완전트리(complete k-ary tree)라고 한다.

그런 트리에 대해서는 노드의 개수를 쉽게 결정할 수 있다.

k진 완전 트리의 깊이와 분기계수가 주어졌을 때 트리의 노드에 번호를 붙일 수 있는 모든 가능한 방법의 수를 결정해야 한다.

이때 각 노드의 레이블은 자손의 레이블보다 작아야 한다.

이진 힙(binary heap)으로 이루어진 우선 순위 큐 자료 구조가 바로 이런 속성을 가진다(이진트리이므로 k=2).

N개의 노드가 있는 트리에 번호를 붙일 때 1에서 N까지의 레이블을 붙일 수 있다고 가정하자.

완전 트리 레이블링 timer 1초 memory 256MB

완전 트리 레이블링 1초 256MB