Insert into a Binary Search Tree

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.

Notice that there may exist multiple valid ways for the insertion, as long as the tree remains a BST after insertion. You can return any of them.

Approach 1: Recursive DFS

class Solution {
    public TreeNode insertIntoBST(TreeNode root, int val) {
        if (root == null)
            return new TreeNode(val);
        if (root.val > val)
            root.left = insertIntoBST(root.left, val);
        else
            root.right = insertIntoBST(root.right, val);
        return root;
    }
}
                

Time Complexity: O(n) and Space Complexity: O(n)

The "Insert into a Binary Search Tree (BST)" problem requires inserting a new value into an existing Binary Search Tree while maintaining its BST properties. The properties of a BST are such that for each node, all elements in the left subtree are smaller, and all elements in the right subtree are larger. The task is to find the correct position for the new value and insert it accordingly.

Problem Statement

Given the root of a Binary Search Tree (BST) and an integer val, insert val into the BST. Return the root node of the BST after the insertion. It is guaranteed that the new value will not be equal to any of the existing values in the BST.

The tree node structure is given above. The task is to insert a new node with the specified value into the BST and return the modified tree's root node.

Approach

The process of inserting a value into a BST involves starting at the root and comparing the value to be inserted with the current node's value. Depending on the comparison:

• If the value to insert is smaller than the current node’s value, we proceed to the left subtree.
• If the value to insert is greater than the current node’s value, we proceed to the right subtree.

This comparison process is repeated recursively until we reach a null spot in the tree, where we can insert the new node.

Algorithm

The algorithm follows these steps:

1. Start at the root of the BST.
2. Compare the value to be inserted with the current node’s value.
3. If the value is smaller, move to the left child; if it is larger, move to the right child.
4. Repeat the process until we find a null spot in the tree where the new node can be inserted.
5. Insert the new node at the null spot.
6. Return the root of the BST after insertion.

This process ensures that the BST properties are maintained during the insertion.

Example

Consider the following Binary Search Tree:

               5
              / \
             3   7
            / \   \
           2   4   8
        

If the value to insert is 6, the BST after insertion will be:

               5
              / \
             3   7
            / \  / \
           2  4 6   8
        

The value 6 is inserted as the left child of the node with value 7, maintaining the BST properties.

Time Complexity

The time complexity of the insertion operation is O(h), where h is the height of the tree. In the worst case, the tree could be unbalanced (like a linked list), and the height would be O(n), where n is the number of nodes in the tree. In the best case (a balanced tree), the height is O(log n).

The space complexity is O(h), where h is the height of the tree, due to the recursive stack used during the traversal.

Optimized Approach

The standard recursive approach works well for most cases. However, an iterative approach can also be used to eliminate the recursive stack and make the process more space-efficient. In the iterative version, we simply loop through the tree starting from the root and move to the left or right child until we find a null spot.

Time Complexity (Iterative Approach)

The time complexity of the iterative approach is also O(h), where h is the height of the tree, as we need to traverse down the tree to find the insertion spot.

The space complexity of the iterative approach is O(1) since we do not use additional space for recursion.

Conclusion

The "Insert into a Binary Search Tree" problem demonstrates how to efficiently insert a new value into a BST while maintaining its properties. Whether using a recursive or iterative approach, the key is to find the correct position for the new value and perform the insertion in such a way that the BST properties are preserved.