701. Insert into a Binary Search Tree

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)