문제

Given the root node of a binary search tree (BST) and a value to be inserted into the tree, insert the value into the BST. Return the root node of the BST after the insertion. It is guaranteed that the new value does not exist in the original BST.

이진 검색 트리(BST)의 root 노드와 트리에 삽입 할 value가 주어지면 value를 BST에 삽입하십시오. 삽입 후 BST의 루트 노드를 반환하십시오. 새 값이 원래 BST에 존재하지 않는 것이 보장됩니다.

Note that there may exist multiple valid ways for the insertion, as long as the tree remains a BST after insertion. You can return any of them.

삽입 후 트리가 BST로 유지되는 한 삽입에 여러 가지 유효한 방법이있을 수 있습니다. 당신은 그들 중 하나를 반환 할 수 있습니다.

For example :

Given the tree:
        4
       / \
      2   7
     / \
    1   3
And the value to insert: 5

You can return this binary search tree:

         4
       /   \
      2     7
     / \   /
    1   3 5

This tree is also valid:

         5
       /   \
      2     7
     / \   
    1   3
         \
          4

5를 BST에 삽입하는 위의 두가지 방법 모두 가능하다.

기본 지식

binary search tree 특징 :

• 이진 트리이기 때문에, 최대 두 개의 자식 노드를 가진다.

• 각 노드의 왼쪽 서브트리에는 그 노드의 값보다 작은 값들을 지닌 노드들로 이루어져 있다.

• 각 노드의 오른쪽 서브트리에는 그 노드의 값과 같거나 큰 값들을 지닌 노드들로 이루어져 있다.

풀이

위의 문제에서는 특별히 전제 조건(예 : 갯수에 비례해 높이를 유지, 등)이 없기 때문에 단순하게 값에 따라 삽입할 위치를 찾아 바로 삽입하는 것으로 문제를 해결하였습니다.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    TreeNode child = null;
    
    public TreeNode insertIntoBST(TreeNode root, int val) {
        
        if(root == null) return new TreeNode(val);
        
        if(val > root.val){
            child = insertIntoBST(root.right, val);
            root.right = child;
        }else{
            child = insertIntoBST(root.left, val);
            root.left = child;
        }
        return root;
    }
}

위와 같이 재귀호출로 구현하였습니다.

BST 특징에 의해 val 값이 root보다 크면 오른쪽 서브트리를 검색하고,

val값이 root보다 작으면 왼쪽 서브트리를 검색해 삽입할 자리를 찾습니다.

삽입할 위치를 child로 return 받아 해당 서브트리 right or left에 연결합니다.( root.right = child )

여기서 재귀호출의 stop condition은

if(root == null) return new TreeNode(val); 입니다.

출처 : 제가 알고리즘 문제에 막 감을 익히고 있는 단계여서 유튜버 승지니어님의 코드를 인용하였습니다. 도움되는 영상이 많이 있으므로 많은 방문 부탁드리겠습니다.

유튜브 승지니어 해당영상