[HackerRank] Tree: Level Order Traversal / Binary Search Tree : Insertion

# Tree: Level Order Traversal  (Trees)

[문제]

 

[코드]

struct node* queue[500];
int front = -1, rear = -1;

void addq(struct node* node)
{
    queue[++rear] = node;
}
struct node* deleteq()
{
    return queue[++front];
}

void levelOrder(struct node *root) {
    struct node* temp;
    
    if(!root) return;
    addq(root);
    while(1)
    {
        temp = deleteq();
        if(!temp) break;
        printf("%d ", temp->data);
        if(temp->left)  addq(temp->left);
        if(temp->right) addq(temp->right);
    }
}

 

[코드설명]

 큐를 사용해서 해결(주어진 코드에서 새로 작성한 코드만 가져옴).

root가 NULL인지 판별하고 NULL이 아니면 큐에 추가.

이후 큐에서 노드 포인터를 delete하고 temp로 받은 다음 NULL인지 판별 후 temp->data 출력.

그리고 temp의 left와 right가 NULL이 아니면 큐에 추가.

empty queue가 될 때까지 위 과정을 반복.

 

[채점 결과]

 

 

 

 

 

# Binary Search Tree : Insertion  (Trees)

[문제]

 

[코드]

struct node* insert(struct node* root, int data) {
    struct node* node = (struct node*)malloc(sizeof(struct node));
    struct node *temp, *prev;
    
    node->data = data;
    node->left = node->right = NULL;
    
    if(root)
    {
        temp = root;
        do{
            prev = temp;
            if(temp->data > data)   temp = temp->left;
            else if(temp->data < data)  temp = temp->right;
            else return NULL;
        } while(temp);
        
        if(prev->data > data) prev->left = node;
        else prev->right = node;
    }
    else
        root = node;
    return root;
}

 

[코드설명]

node에 트리에 새로 추가할 노드를 만든다.

root가 NULL이라면 empty tree이므로 root에 node를 추가한다.NULL이 아니라면 트리를 따라 맨 아래로 내려간다.temp를 사용해서 노드를 탐색하는데 새로 추가 할 노드의 data가 더 작으면 left, 더 크면 right로 이동한다.같다면 중복이므로 NULL을 return한다.temp가 NULL이라면 트리의 맨 아래까지 왔다는 뜻이므로 do-while문을 빠져나오고 prev의 자식에 node를 추가한다.data가 prev의 data보다 작으면 left, 크면 right에 추가한다.모든 과정이 끝나면 root를 return한다. 

 

[채점 결과]