Leetcode 701. Insert into a Binary Search Tree

Problem

Leetcode 701 - Insert into a Binary Search Tree

Example:

Input: root = [4,2,7,1,3], val = 5
Output: [4,2,7,1,3,5]

Input: root = [40,20,60,10,30,50,70], val = 25
Output: [40,20,60,10,30,50,70,null,null,25]

Input: root = [4,2,7,1,3,null,null,null,null,null,null], val = 5
Output: [4,2,7,1,3,5]

Approach

Since we’re working with BST, we can implement this like a binary search, meaning if val is less than curr.val then we move left. If val is greater than curr.val we move right. We simply add a TreeNode if left/right doesn’t exist.

Here is the Python code for the solution:

class Solution:
    def insertIntoBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
        if not root:
            return TreeNode(val)

        curr = root

        while curr:
            if val < curr.val:
                if curr.left:
                    curr = curr.left
                else:
                    curr.left = TreeNode(val)
                    return root
            else:
                if curr.right:
                    curr = curr.right
                else:
                    curr.right = TreeNode(val)
                    return root

Time Complexity and Space Complexity

Time Complexity: $O(h)$ where $h$ is the height of the tree

Space Complexity: $O(1)$