[Geeks for Geeks] Insert a node in a BST

🔒 문제

그냥 Binary Search Tree 에 원소를 대입하는 문제다.

 

💭 생각의 흐름

중복을 허용하지 않기 때문에 같은 Key 값을 발견하면 바로 root를 리턴한다.

최종 삽입위치에 노드를 생성하고 부모가 자식을 가리키는 포인터를 지정해야 하므로

자식 노드로 내려갈 때마다 부모 노드를 킵해야한다.

 

🔑 풀이

Node* insert(Node* root, int Key)
{
    Node* parent = root;
    Node* tempNode = root;
    
    while (tempNode != nullptr) {
        parent = tempNode;
        if (Key == tempNode->data) return root;
        else tempNode = (Key < tempNode->data) ? tempNode->left : tempNode->right;
    }
    
    if (parent->data > Key) parent->left = new Node(Key);
    else if (parent->data < Key) parent->right = new Node(Key);

    return root;
}

 

 

심심해서 특정 원소를 찾는 find 함수까지 작성했다.

Node* find(Node* root, int key) {
    Node* parent = root;
    
    while (root != nullptr) {
        if (key == root->data) return root;
        else {
            parent = root;
            root = (key < root->data) ? root->left : root->right;
        }
    }
    
    return root;
}

 

---

Binary Search Tree (BST)는 Set , Heap, Priority Queue 구현에 활용된다.

이중에 Set 은 중복을 허용하지 않고  Heap, Priority Queue는 중복을 허용한다.