[해커랭크] Binary Search Tree : Insertion (C++)

문제 링크: www.hackerrank.com/challenges/binary-search-tree-insertion/problem?h_r=internal-search

Binary Search Tree : Insertion | HackerRank

1. 주의할 점

- 파라미터로 받은 Root가 NULL이라면?

- BST에 새로운 Node(Data)를 추가할 때, 가장 아래에 추가하는데 어떤 방식으로 접근해야 하는가?

 

2. 구현

- BST에 새로운 Node(Data)를 추가할 때, 가장 아래에 추가하는데 어떤 방식으로 접근해야 하는가?에 대한 대답으로는 기존의 BST에서 Data를 Search하여 NULL에 도달하는 곳에 추가한다

- BST에서 특정 Data를 검색하는 방법으로는 Root부터 검사하여 해당 Node의 값보다 작으면 왼쪽, 크면 오른쪽 Subtree를 검사한다. 단, 이 Subtree가 nullptr이라면 새로운 Node를 하나 생성한 이후, 추가한다

Node * insert(Node * root, int data) {
        if(root==NULL){
            Node* n = new Node(data);
            return n;
        }
        Node *node = root;
        while (node) {
            int cur = node->data;
            if (data < cur){
                if(node->left!=nullptr)
                    node = node->left;
                else{
                    Node* n = new Node(data);
                    node->left = n;
                    break;
                }
            }
            else{
                if(node->right!=nullptr)
                    node = node->right;
                else{
                    Node* n = new Node(data);
                    node->right = n;
                    break;
                }
            }
        }       
        return root;
    }