701. Insert into a Binary Search Tree

# Medium

Solution 1: (add new value to leaf, don't change root)

1. Use helper function to insert new value as a leaf

2. Return original root in main function

Java(I)

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

Java(II)simple

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

Python

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def insertIntoBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
        # ege case
        if not root:
            return TreeNode(val)
        
        # regular case
        curr = root
        while True:
            if val > curr.val:
                if not curr.right:
                    curr.right = TreeNode(val)
                    break
                else:
                    curr = curr.right
            else:
                if not curr.left:
                    curr.left = TreeNode(val)
                    break
                else:
                    curr = curr.left
                    
        return root