## Similar Problems

Similar Problems not available

# Insert Into A Binary Search Tree - Leetcode Solution

LeetCode: Insert Into A Binary Search Tree Leetcode Solution

Difficulty: Medium

Topics: binary-search-tree tree binary-tree

Problem Statement:

You are given the root node of a binary search tree (BST) and a value to insert into the tree. Return the root node of the BST after the insertion. It is guaranteed that the new value does not exist in the original BST.

Approach:

We can solve this problem in two ways; recursive and iterative approach.

Recursive Approach:

In the recursive approach, we will traverse through the BST from the root node and will compare the value to insert with the current node's value.

If the value to insert is greater than the current node's value, then we will move to the right subtree, else we will move to the left subtree.

We will continue this process until we reach a leaf node.

At the leaf node, we will create a new node with the given value and attach it to the BST.

Then we will return the root node of the BST.

In the code below, we can see the implementation of the recursive approach.

```
class Solution:
def insertIntoBST(self, root: TreeNode, val: int) -> TreeNode:
# If the root is None, then create a new node with the given value and return it.
if root is None:
return TreeNode(val)
# If the value to insert is greater than the root's value, then move to the right subtree.
if val > root.val:
root.right = self.insertIntoBST(root.right, val)
# If the value to insert is less than the root's value, then move to the left subtree.
else:
root.left = self.insertIntoBST(root.left, val)
# Return the updated root node.
return root
```

Iterative Approach:

In the iterative approach, we will also traverse through the BST from the root node and will compare the value to insert with the current node's value.

If the value to insert is greater than the current node's value, then we will move to the right subtree, else we will move to the left subtree.

We will continue this process until we reach a leaf node.

At the leaf node, we will create a new node with the given value and attach it to the BST.

Then we will return the root node of the BST.

In the code below, we can see the implementation of the iterative approach.

```
class Solution:
def insertIntoBST(self, root: TreeNode, val: int) -> TreeNode:
# If the root is None, then create a new node with the given value and return it.
if root is None:
return TreeNode(val)
# Traverse through the BST from the root node.
node = root
while node:
# If the value to insert is greater than the node's value, then move to the right subtree.
if val > node.val:
if node.right:
node = node.right
else:
node.right = TreeNode(val)
return root
# If the value to insert is less than the node's value, then move to the left subtree.
else:
if node.left:
node = node.left
else:
node.left = TreeNode(val)
return root
# Return the root node of the BST.
return root
```

Both, the recursive and iterative approaches will give the same output. Also, both the approaches have the same time and space complexity.

Time Complexity: O(h), where h is the height of the BST.

Space Complexity: O(1) in the iterative approach and O(h) in the recursive approach due to the internal stack used by the recursion.

## Insert Into A Binary Search Tree Solution Code

`1`