Binary search tree: insert

Build a BST one key at a time. Smaller keys go left, larger keys go right.

Time O(h)Space O(h)Code C++, Python and C#

Watch it animatedStep through it, with the running line highlighted. Free with an account.

The idea

Start at the root and compare. Go left if the new key is smaller, right otherwise, until you fall off the tree. That empty spot is where the key belongs.

Code

C++PythonC#

TreeNode* insert(TreeNode* root, int key) {
    if (!root) return new TreeNode(key);
    if (key < root->val)
        root->left = insert(root->left, key);
    else
        root->right = insert(root->right, key);
    return root;
}

def insert(root: TreeNode | None, key: int) -> TreeNode:
    if root is None: return TreeNode(key)
    if key < root.val:
        root.left = insert(root.left, key)
    else:
        root.right = insert(root.right, key)
    return root

public static TreeNode Insert(TreeNode root, int key) {
    if (root == null) return new TreeNode(key);
    if (key < root.val)
        root.left = Insert(root.left, key);
    else
        root.right = Insert(root.right, key);
    return root;
}

Tips

h is the height. A balanced tree has h ≈ log n, but inserting sorted keys makes a chain with h = n.
Try entering 10, 20, 30, 40, 50 to see the worst case.

In the .NET library

SortedSet<T> and SortedDictionary<TKey,TValue> are red-black trees. They rebalance on every insert, so h stays O(log n).