> For the complete documentation index, see [llms.txt](https://r24zeng.gitbook.io/leetcode-notebook/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://r24zeng.gitbook.io/leetcode-notebook/wan-quan-an-zhao-jiu-zhang-suan-fa-shua-de-60-dao-zuo-you/iii.-binary-tree/701.-insert-into-a-binary-search-tree.md).

# 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

{% tabs %}
{% tab title="Java(I)" %}

```java
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;
    }
}
```

{% endtab %}

{% tab title="Java(II)simple" %}

```java
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;
    }
}
```

{% endtab %}

{% tab title="Python" %}

```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
```

{% endtab %}
{% endtabs %}