[leetcode #701] Insert into a Binary Search Tree

Problem

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

Notice 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.

Example 1:

Input: root = [4,2,7,1,3], val = 5
Output: [4,2,7,1,3,5]
Explanation: Another accepted tree is:

Example 2:

Input: root = [40,20,60,10,30,50,70], val = 25
Output: [40,20,60,10,30,50,70,null,null,25]

Example 3:

Input: root = [4,2,7,1,3,null,null,null,null,null,null], val = 5
Output: [4,2,7,1,3,5]

Constraints:

・ The number of nodes in the tree will be in the range [0, 10⁴].
・ -10⁸ <= Node.val <= 10⁸
・ All the values Node.val are unique.
・ -10⁸ <= val <= 10⁸
・ It's guaranteed that val does not exist in the original BST.

Idea

BST의 원리만 이해하면 쉽게 풀 수 있다.

BST에 노드가 하나도 없을 경우 val 값으로 노드를 만들어 리턴한다.

BST에 노드가 있다면 val과 크기를 비교해서 null인 노드가 나올 때까지 탐색한다. val이 현재 노드보다 작으면 왼쪽 자식 노드를, 크면 오른쪽 자식 노드로 이동한다. 만약 자식 노드가 없다면 val로 새로운 노드를 만들어 연결해주면 된다.

만약 값이 같은 노드가 있을 경우 곧바로 리턴해서 새로운 노드가 생기지 않도록 한다.

Solution

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

        traverseBST(root, val);

        return root;
    }

    private void traverseBST(TreeNode node, int val) {
        if (val < node.val) {
            if (node.left == null) {
                node.left = new TreeNode(val);
            } else {
                traverseBST(node.left, val);
            }
        } else if (val > node.val) {
            if (node.right == null) {
                node.right = new TreeNode(val);
            } else {
                traverseBST(node.right, val);
            }
        } else {
            return;
        }
    }
}

Reference

https://leetcode.com/problems/insert-into-a-binary-search-tree/