이진 탐색 트리(BST) timer 2초 memory 128MB

트리의 각 노드가 갖는 자식노드의 수가 두 개 이하인(0, 1, 2중에 하나) 트리를 이진트리라고 한다.

이진트리에 아래와 같은 규칙으로 노드의 값이 저장된 트리를 이진 탐색 트리라고 한다.

• 어떤 노드에 저장된 수가 A라면,

• 그 노드의 왼쪽 서브트리에 속한 노드(들)에는 A보다 작은 수(들), 

• 오른쪽 서브트리에 속한 노드(들)에는 A보다 큰 수(들)만 저장된다.

각 노드에 양의 정수 하나를 담고있는 이진 트리가 있을 때, 이 트리에 정수를 추가하는 문제를 생각해보자.

1. N개의 양의 정수가 주어진다. 주어진 모든 양의 정수는 서로 다르며 1~N 사이의 정수이다.

2. 이제 주어진 첫 번째 수를 루트 노드로 놓고, 다른 나머지 수들을 순서대로 삽입하면서 이진 탐색 트리를 만들려고 한다.

3. 다시 말해, 첫 번째 수를 제외한 모든 수에 대해서 insert(노드, 정수) 함수를 실행하는 것과 같다. 

   • insert(노드, 정수) 함수는 아래와 같이 설명된다.

     insert(노드 now, 정수 num):
         개수 cnt를 1 증가시킨다
         if num이 노드 now에 저장된 수보다 작다면 :
             if now의 왼쪽 자식이 없는 경우:
                 num을 저장하는 새 노드를 만든 뒤, now의 왼쪽 자식으로 만든다.
             else :
                 insert(now의 왼쪽 자식 노드, num)
         else :  // 노드 now에 저장된 수보다 num이 크다면
             if now의 오른쪽 자식이 없는 경우:
                 num을 저장하는 새 노드를 만든 뒤, now의 오른쪽 자식으로 만든다.
             else :
                 insert(now의 오른쪽 자식 노드, num)

 새로운 수를 이진탐색트리에 추가할 때 마다 누적된 cnt값을 출력하는 프로그램을 작성하시오.