[HackerRank] Binary Search Tree : Insertion

https://www.hackerrank.com/challenges/binary-search-tree-insertion/problem

Binary Search Tree : Insertion | HackerRank

이진 탐색 트리에서 노드를 하나씩 삽입할때마다 트리를 재구성해야한다.

 

이진 탐색 트리의 조건은 다음과 같다.

1. 트리의 모든 원소는 중복없이 유일

2. 루트노드는 왼쪽 서브트리보다 값이 커야하고 오른쪽 서브트리보다 값이 작아야한다.

3. 왼쪽 서브트리, 오른쪽 서브트리 모두 이진 탐색 트리

 

따라서 먼저 노드를 삽입할때 트리가 비어있는지를 확인을해야한다.

두번째는 겹치는 노드가 있는지, 값이 작은지, 큰지를 비교한다.

 

문제에서는 insert 될 때의 코드만 작성하라고 되어있기 때문에 insert 될때의 코드만 작성했다.

node라는 변수에는 data를 저장해주고 prev는 이전의 노드(상위 노드), temp는 현재 노드를 나타낸다.