Broken BST

Let T를 임의의 이진 트리, 즉 모든 정점이 최대 두 개의 자식을 갖는 트리라고 하자. 주어진 트리는 루트가 있는 트리이므로 부모가 없는 정점은 단 하나만 존재하며t, 그 정점이 트리의 루트이다. 모든 정점에는 정수가 하나씩 적혀 있다. 다음 알고리즘을 트리 T의 모든 value에 대해 실행한다.

1. 포인터를 트리의 루트로 설정한다.
2. 현재 정점의 value이 찾고 있는 수와 같으면 성공을 반환한다.
3. 현재 정점의 value이 찾고 있는 수보다 크면 그 정점의 왼쪽 자식으로 이동한다.
4. 현재 정점의 value이 찾고 있는 수보다 작으면 그 정점의 오른쪽 자식으로 이동한다.
5. 존재하지 않는 정점으로 이동하려 하면 실패를 반환한다t.

설명한 알고리즘의 의사 코드는 다음과 같다.

bool find(TreeNode t, int x) {  
    if (t == null)  
        return false;  
    if (t.value == x)  
        return true;  
    if (x < t.value)  
        return find(t.left, x);  
    else  
        return find(t.right, x);  
}  
find(root, x);  

설명한 알고리즘은 트리가 이진 탐색 트리인 경우(즉, 각 노드에서 왼쪽 서브트리의 값들은 그 노드의 value보다 작고 오른쪽 서브트리의 값들은 그 노드의 value보다 큰 경우) 올바르게 동작한다. 하지만 트리가 이진 탐색 트리가 아니라면 잘못된 결과를 반환할 수 있다.

주어진 트리가 반드시 이진 탐색 트리인 것은 아니므로 이 방법으로 모든 수를 찾을 수 있는 것은 아니다. 트리의 모든 value에 대해 탐색을 실행했을 때 탐색이 실패하는 횟수를 구한다.

트리에 같은 값이 적힌 정점이 여러 개 있다면, 그 각각에 대해 알고리즘을 별도로 실행해야 한다.

첫째 줄에 정수 n (1 ≤ n ≤ 105)이 주어진다. 트리의 정점 수이다.

다음 n개 줄에는 각각 3개의 수 v, l, r (0 ≤ v ≤ 109)이 주어진다. 각각 현재 정점의 value, 그 정점의 왼쪽 자식 인덱스, 오른쪽 자식 인덱스를 나타낸다. 어떤 자식이 존재하지 않으면t 그 대신 - 1이 주어진다. 트리의 서로 다른 정점에 같은 값이 들어 있을 수도 있음에 유의한다.

탐색 알고리즘이 실패하는 횟수를 출력한다.

예제에서 트리의 루트는 정점 2에 있다. 수 5와 15를 탐색하면 실패를 반환한다. 첫 단계에서 알고리즘이 찾고 있는 수를 포함하지 않는t 서브트리를 선택하기 때문이다.