Insert into a Binary Search Tree — Editorial

Opening the reading…

Intuitionthe ordering rule identifies one safe leaf position

In a binary search tree, every value smaller than a node belongs somewhere in its left subtree, while every larger value belongs somewhere in its right subtree. Start at the root and compare the value you need to insert with the current node. The comparison tells you which entire subtree can possibly contain the correct position, so the other subtree can be ignored.

Continue in the chosen direction until that child pointer is null. That empty pointer is the insertion point: placing the new node there keeps it below every ancestor that led you there. Because the value is absent and only a leaf is added, no existing node needs to move, and the original root remains the answer unless the original tree is empty.

Approach

Create the new node before searching, because every successful insertion needs exactly one leaf and the empty-tree case can return it immediately.

If root is null, return the new node, because there is no existing node whose child pointer can receive it and the new node itself must become the root.

Keep a pointer cur at the root and compare val with cur->val at each step, because the BST property tells you whether the only possible destination is in the left or right subtree.

When val is smaller, move cur to its left child if that child exists; otherwise attach the new node to cur->left, because a missing left child is the first valid position in that direction.

When val is larger, move cur to its right child if that child exists; otherwise attach the new node to cur->right, because a missing right child is the first valid position in that direction.

Stop immediately after attaching the node, because the insertion is complete and continuing would risk following a pointer from the newly created leaf.

Return root rather than cur, because cur is only the search pointer and the caller still needs the original tree root.

Complexitythe search follows one root-to-leaf path

MEASURE	BOUND	WHY
Time	O(h), worst case O(n)	Each loop iteration moves exactly one level downward and never revisits a node, so the number of comparisons equals the length of one root-to-leaf path. A skewed tree has height n - 1, giving the worst-case O(n) bound.
Space	O(1) extra	Only cur and the already allocated new node use auxiliary storage; the returned tree, including its new node, is required output and is excluded. The bound stays O(1) even for a skewed tree because the iterative search does not store the path.

Here n is the number of nodes in the original tree and h is its height, measured as the maximum number of child links on a root-to-leaf path.

Annotated solutionC++ · iterative · one downward walk and one attachment

CPPIteratively follow the matching subtree and attach the new leaf at the first empty child pointer.

#include <iostream>
using namespace std;

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) {
        TreeNode* newNode = new TreeNode(val);
        if (root == nullptr) {
            return newNode;
        }

        TreeNode* cur = root;
        while (true) {
            if (val < cur->val) {
                if (cur->left != nullptr) {
                    cur = cur->left;
                } else {
                    cur->left = newNode;
                    break;
                }
            } else {
                if (cur->right != nullptr) {
                    cur = cur->right;
                } else {
                    cur->right = newNode;
                    break;
                }
            }
        }

        return root;
    }
};

The two branches differ only in which child pointer they inspect. If that pointer is present, cur advances one level; if it is absent, the new node is attached and the loop ends. The return value is deliberately root, not cur: cur identifies the parent where the insertion happened, while root is the handle that still reaches every node in the tree.

The recursive alternativeshorter control flow, but the path moves onto the call stack

CPPRecursive insertion returns each unchanged subtree root after inserting below it.

#include <iostream>
using namespace std;

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 == nullptr) {
            return new TreeNode(val);
        }

        if (val < root->val) {
            root->left = insertIntoBST(root->left, val);
        } else {
            root->right = insertIntoBST(root->right, val);
        }

        return root;
    }
};

This is a different arrangement of the same search, not an optimisation. The base case creates the node exactly where the current subtree is empty. Each caller assigns the returned subtree root back to its left or right child, which preserves the link while the recursion unwinds. The code is concise, but its extra space is O(h) for the call stack, reaching O(n) in a skewed tree.