First, use a binary search to find the largest node which is smaller than the inserting value. Then, use this value to replace the found node, and add its right sub-tree to the right of the inserted one.

```
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def insertIntoBST(self, root: TreeNode, val: int) -> TreeNode:
new = TreeNode(val)
if root is None:
return new
# Find the closest node to the inserting value which is smaller than it
closest = None
diff = float('inf')
tmp = root
while tmp:
if tmp.val > val:
tmp = tmp.left
else:
if diff > val - tmp.val:
diff = val - tmp.val
closest = tmp
tmp = tmp.right
if closest is None:
# All nodes in the tree is greater than val
new.right = root
return new
new.right = closest.right
closest.right = new
return root
```