Insert into a Binary Search Tree

How it works

The iterative approach follows the same logic as recursion but uses a loop instead of the call stack. We traverse down the tree, comparing values at each node to decide which direction to go. When we find a null child in the direction we need to go, we've found the insertion point. We create the new node and attach it directly. This approach uses O(1) extra space since we don't need the recursion stack, making it more memory-efficient for deep trees.

Steps

1. If root is null, return a new node with the given value.
2. Start with cur pointing to the root.
3. Loop indefinitely:
   • If val is greater than cur.val, check if cur.right is null. If so, insert the new node there and return the root. Otherwise, move cur to cur.right.
   • If val is less than or equal to cur.val, check if cur.left is null. If so, insert the new node there and return the root. Otherwise, move cur to cur.left.

Complexity

• Time complexity: O(h)
• Space complexity: O(1) extra space.

Where h is the height of the given binary search tree.

Things to watch for

Forgetting to Return the New Node for Empty Trees

When the tree is empty (root is null), failing to create and return a new node with the given value results in returning null instead of the single-node tree. The base case must explicitly handle this by returning new TreeNode(val).

Not Linking the New Node Back to the Parent

In the iterative approach, inserting the new node without properly linking it to the parent's left or right pointer means the node is created but never connected to the tree. The new node must be assigned to either cur.left or cur.right based on the comparison.

Incorrect Comparison Direction

Comparing values with the wrong inequality operator (e.g., using < instead of >) causes nodes to be inserted on the wrong side of the tree, violating the BST property. Values greater than the current node must go right, and values less than or equal must go left.

from typing import Optional

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def insertIntoBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
        if not root:
            return TreeNode(val)

        cur = root
        while True:
            if val > cur.val:
                if not cur.right:
                    cur.right = TreeNode(val)
                    return root
                cur = cur.right
            else:
                if not cur.left:
                    cur.left = TreeNode(val)
                    return root
                cur = cur.left

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* insertIntoBST(TreeNode* root, int val) {
        if (!root) {
            return new TreeNode(val);
        }

        TreeNode* cur = root;
        while (true) {
            if (val > cur->val) {
                if (!cur->right) {
                    cur->right = new TreeNode(val);
                    return root;
                }
                cur = cur->right;
            } else {
                if (!cur->left) {
                    cur->left = new TreeNode(val);
                    return root;
                }
                cur = cur->left;
            }
        }
    }
};