# Approach 1: Recursively insert into left or right parts

`# Definition for a binary tree node.# class TreeNode(object):#     def __init__(self, x):#         self.val = x#         self.left = None#         self.right = Noneâ€‹class Solution(object):    def insertIntoBST(self, root, val):        """        :type root: TreeNode        :type val: int        :rtype: TreeNode        """        if root == None: return TreeNode(val)        if val > root.val:            root.right = self.insertIntoBST(root.right, val)        else:            root.left = self.insertIntoBST(root.left, val)        return root`

Time Complexity: O(logN) assuming balanced BST (Otherwise O(N) worst case where N is number of nodes)

Space Complexity: O(M) height of the stack (recursive call)

# Approach 2: Iterative Approach 1

`# Definition for a binary tree node.# class TreeNode(object):#     def __init__(self, x):#         self.val = x#         self.left = None#         self.right = Noneâ€‹class Solution(object):    def insertIntoBST(self, root, val):        """        https://leetcode.com/problems/insert-into-a-binary-search-tree/description/        :type root: TreeNode        :type val: int        :rtype: TreeNode        """        parser = root        prevParser = root        while parser:                               if val > parser.val:                prevParser = parser                parser = parser.right            else:                prevParser = parser                parser = parser.left        if val > prevParser.val:            prevParser.right = TreeNode(val)        else:            prevParser.left = TreeNode(val)        return root`

We iterate through the tree and each time eliminate half the tree based on the value of the current node we are on. If the value to be inserted is greater than current node's value we move to the right tree and vice versa. By the time we finish iterating like this we reach the position where the node is supposed to inserted. We insert it in it's position using the `TreeNode prevParser` which stores the position of the parser one iteration behind i.e. the parent node

Time Complexity: O(logN) assuming balanced BST (Otherwise O(N) worst case where N is number of nodes)

Space Complexity: O(1)