문제의 설명을 그대로 구현하면 O(N²)이라서 시간초과가 납니다. 아예 새로운 방법을 찾아야 합니다.

우선 각 노드가 어떤 깊이에 들어가는지 규칙을 찾는 것이 첫 번째 과정입니다.

저렇게 구현하는 것만 배웠고 다른 방법은 아예 모르는데 생각좀 하면 풀수 있을만한 문제 인가요? 

네. 힌트를 드리자면, 수를 넣을 때마다 각 수가 들어간 깊이를 써 보세요. 예제 입력의 경우 이렇게 나오겠죠.

그리고 std::map을 아신다면 이게 큰 도움이 됩니다.

사실 꽤 어려운 문제긴 합니다.

아 감사합니다 한번 해볼께요

저도 이문제 때문에 계속 헤매고 있는데요

"우선 각 노드가 어떤 깊이에 들어가는지 규칙을 찾는 것" 이 어떤 알고리즘일까요? ㅠ.ㅠ

제 답변을 이해하지 못하였다는 뜻인가요, 규칙을 모르겠다는 뜻인가요?

네, 규칙을 몰라서요ㅠ.ㅠ

말씀하시는 대략적인 알고리즘이, 

"새로운 값을 넣을 때마다 그 값에 해당하는 노드의 깊이를 구해서 N*N 배열에 깊이 값을 저장한다 (새로운 값이 배열의 열의 위치)" <-- 이렇게 이해했구요

이때, 새로운 값을 넣을때 그 값에 해당하는 노드의 깊이를 어떤 규칙으로 찾는건지 감이 안와서요^^

예제는 규칙을 알아낼 수 있을 만큼 크지 않습니다. N=30 정도의 데이터를 랜덤으로 만들어서 돌려 보면 괜찮을 것 같네요.

한 가지 힌트를 더 드리자면, x를 트리에 넣으면 "x에 가까운 수"의 자식 노드로 들어가게 됩니다.

jh0513님이 힌트 주신 방법대로 해봐도 시간 초과네요 ㅠ.ㅠ

제가 의도한 규칙이 맞다면 그 규칙을 std::map으로 O(nlogn)만에 구현할 수 있습니다. C++ 말고 C에 이게 있는지는 모르겠네요.

jh5013님

감사합니다. 덕분에 이진트리를 링크드리스트가 아닌 배열로 짜보는 공부를 잘 했던거 같습니다.

저는 요정도까지만 해도 많이 배운것 같습니다.