루트가 있는 이진 트리를 생각하자. 이 트리의 단말 정점은 개이며, 모든 내부 정점에는 정확히 두 개의 자식이 있다.
단말 정점에는 트리를 중위 순회할 때 방문되는 순서대로 의 번호가 붙어 있다.
두 단말 정점 , 사이의 거리 는 에서 로 가는 단순 경로에 포함된 간선의 수로 정의한다.
이 트리에서 각 에 대한 의 값은 아래 표와 같다.
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | |
|---|---|---|---|---|---|---|---|
| 2 | 6 | 3 | 2 | 4 | 3 | 4 |
위 표의 값을 만족하는 트리는 유일하게 결정된다. 의 값을 구하라.