# Insert into a Binary Search Tree | LeetCode 701 | Python | Solution

#### Concept

This is clearly a Tree related problem and a medium-type problem. In my sense, it’s not that difficult if you have a basic concept about BST (Binary Search Tree). BST is also a Binary Tree.

So what is a Binary Search Tree? BST is a type of Binary Tree, where the left subtree of a node contains equal or smaller values, and the right subtree contains equal or greater values. BST is also known as sorted Tree.

In this problem, we will be given a root node of a BST and a value to insert into the tree by maintaining the BST rules. After that, we will return the root node of the given tree.

To solve this problem, we have to search for a valid place for the given value. For that, we have to traverse through the tree. if `val < node.val`, then we will go to the left. Before going to the left, we will check that if there is no left child, create a TreeNode with the given value in that place. And our job is done.

For `val > node.val`, we will do the exact opposite thing.

We can solve this problem in many ways using the iterative method or recursive method.

#### Coding Part

Iterative Solution

```class Solution:
def insertIntoBST(self, root: TreeNode, val: int) -> TreeNode:

if root is None:
return TreeNode(val)

current = root

while current:
if val < current.val:
if current.left is None:
current.left = TreeNode(val)
break

current = current.left
else:
if current.right is None:
current.right = TreeNode(val)
break

current = current.right

return root```

Recursive Solution

```class Solution:
def insertIntoBST(self, root: TreeNode, val: int) -> TreeNode:

if root is None:
return TreeNode(val)

if val < root.val:
root.left = self.insertIntoBST(root.left, val)
else:
root.right = self.insertIntoBST(root.right, val)

return root```

#### Last Words

If you submit these codes on LeetCode, these got accepted. But you should never submit any code if you don’t understand the solution.

So I hope this gives you a bit of an idea of this problem solution.