Recursive method to realize the insertion operation in binary search tree

701. Insert operation in binary search tree

difficulty ： secondary

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 .

Ideas

towards BST When inserting a value in, you need to determine the size of the inserted value and the value of the current node

• If the insertion value is less than the value of the current node , Then find the right position in the left subtree of the current node
• If the insertion value is greater than the value of the current node , Then find a suitable position in the right subtree of the current node

If the code of solution one below is difficult to understand , You can look at the code of solution 2 first

Solution 1 ：

package cn.edu.xjtu.carlWay.tree.insertIntoBST;

import cn.edu.xjtu.Util.TreeNode.TreeNode;

/** * 701.  Insert operation in binary search tree  *  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 . * <p> *  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  . * <p> * https://leetcode-cn.com/problems/insert-into-a-binary-search-tree/ */
class Solution {
    
    public TreeNode insertIntoBST(TreeNode root, int val) {
    
        if (root == null) //  If the current node is empty , That means val Found the right place , At this point, the created node returns directly to .
            return new TreeNode(val);
            
        if (root.val < val){
    
            root.right = insertIntoBST(root.right, val); //  Recursively create the right subtree 
        }else if (root.val > val){
    
            root.left = insertIntoBST(root.left, val); //  Recursively create left subtree 
        }
        return root;
    }
}

Solution 2 ：

If the left child node is empty, insert , If it's not empty, keep looking , The same goes for the right side

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