[HackerRank] Tree- Binaery Search Tree: Insertion

Binary Search Tree : Insertion | HackerRank

Binary Search Tree : Insertion | HackerRank

 

<문제>

input) 하나의 tree와 insert하고 싶은 숫자

output) 입력한 숫자가 tree에 삽입되고 난 결과

 

<코드>

struct node* insert( struct node* root, int data ) {
	struct node * node2 = (struct node*)malloc(sizeof(struct node));
    node2->data = data;
    node2->left=node2->right = NULL;
    if(!root){
        return node2;
    }
    struct node* tmp = root;
    while(1){
        if(data > tmp->data){
            if(tmp->right){
            tmp = tmp->right;
            }
            else if(!tmp->right){
                tmp->right = node2;
                break;
            }
        }
        if(data < tmp->data){
            if(tmp->left){
            tmp = tmp->left;
            }
            else if(!tmp->left){
                tmp->left = node2;
                break;
            }
        }
    }
    return root;
	
}

 

<코드 풀이>

먼저 트리에 숫자를 insert하기 위해 새로운 노드 node2를 생성하였다.

node2의 data에는 우리가 insert하고 싶은 숫자 data를 저장하고, left와 right에는 각각 NULL을 저장한다.

또한 tmp포인터가 root를 가리키게 하여 우리가 원래 트리에 insert하고 싶은 숫자 data가 tmp->data보다 큰지 작은지에 따라 right로 갈지 left로 갈지 결정된다. 만약 data가 더 크다면 right로 가고, 더 작다면 left로 간다.

while반복문을 통해 계속 비교하여 right, left중 한 곳으로 가다가 tmp->right 또는 tmp->left가 비어있으면 그 때 node2를 삽입하고 반복문을 빠져나오게 하여 문제를 풀 수 있었다. 

 

<결과>