Insert Into A Binary Search Tree - Leetcode Solution

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.

1