Leetcode 701 insertion operation in binary search tree -- recursive method and iterative method

source ： Power button （LeetCode）
link ：https://leetcode-cn.com/problems/insert-into-a-binary-search-tree

---

The question ：

Given a binary search tree （BST） The root node root And the value to be inserted into the tree value , Insert values into a binary search tree . Return to the root node of the binary search tree after insertion . input data Guarantee , The new value is different from any node value in the original binary search tree .

Be careful , There may be many effective insertion methods , As long as the tree remains a binary search tree after insertion . You can go back to Any valid result .

Example 1：

Input ：root = [4,2,7,1,3], val = 5
Output ：[4,2,7,1,3,5]
explain ： Another tree that meets the requirements of the topic 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]

Tips ：
The number of nodes in the tree will be [0, 10⁴] Within the scope of .
-10⁸ <= Node.val <= 10⁸
All worth Node.val yes unique Of .
-10⁸ <= val <= 10⁸
Guarantee val In primitive BST Does not exist in the .

---

Reference article

Ideas ：

In fact, I don't quite understand why this problem is classified as medium difficulty , Quite a simple question .

As long as you understand the concept of binary search tree , Search from the root node of the binary search tree , Until the location found is an empty node , Let's replace this empty node with a node with the value to be inserted .

We use recursive method and iterative method to solve this problem .

Recursive method Java Code ：

class Solution {
    
    public TreeNode insertIntoBST(TreeNode root, int val) {
    
        if (root == null) {
    
            TreeNode node = new TreeNode(val);
            return node;
        }
        if (root.val > val) root.left = insertIntoBST(root.left, val);
        if (root.val < val) root.right = insertIntoBST(root.right, val);
        return root;
    }
}

Iterative method Java Code ：

class Solution {
    
    public TreeNode insertIntoBST(TreeNode root, int val) {
    
        if (root == null) return new TreeNode(val);
        TreeNode parent = root;
        TreeNode cur = root;
        while (cur != null) {
    
            parent = cur;
            if (cur.val > val) cur = cur.left;
            else if (cur.val < val) cur = cur.right;
        }
        if (parent.val > val) parent.left = new TreeNode(val);
        else if (parent.val < val) parent.right = new TreeNode(val);
        return root;
    }
}