The challenge
Insert a key while preserving the strict BST ordering rule and return the updated root.
Duplicate keys are ignored. Insertion mutates the tree and does not rebalance it.
Example
Key 5 becomes the left child of E:6. Inserting 7 into an empty tree creates the root.
Use the walkthrough below to inspect the input and each state change.
See BST insertion, step by step
Follow the branches. Watch the state change.
View child pointers & node state
| Node | Value | Left | Right | State |
|---|---|---|---|---|
| A | 8 | B | C | — |
| B | 4 | D | E | — |
| C | 12 | F | G | — |
| D | 2 | null | null | — |
| E | 6 | null | null | — |
| F | 10 | null | null | — |
| G | 14 | null | null | — |
Inspect the input.
Labels identify node objects; numbers are their values. Left and right child pointers define the tree.
root = A:8View original input
A:8 [L:B, R:C] · B:4 [L:D, R:E] · C:12 [L:F, R:G] · D:2 [L:null, R:null] · E:6 [L:null, R:null] · F:10 [L:null, R:null] · G:14 [L:null, R:null]
Key: 5
Node IDs stay distinct even when values repeat. Pointer mutations update the diagram; removed nodes remain in the state table for reference.
Put it into code
A recursive call returns the root that must be reattached to the chosen child pointer.
Nodes store value, left, and right. C++ uses C++17 or later.
from collections import deque
class Node:
def __init__(self, value, left=None, right=None):
self.value = value
self.left = left
self.right = right
def bst_insert(root, key):
if root is None:
return Node(key)
if key < root.value:
root.left = bst_insert(root.left, key)
elif key > root.value:
root.right = bst_insert(root.right, key)
return root
#include <algorithm>
#include <cmath>
#include <functional>
#include <limits>
#include <map>
#include <optional>
#include <queue>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <vector>
using namespace std;
struct Node {
long long value;
Node *left = nullptr, *right = nullptr;
explicit Node(long long v) : value(v) {}
};
Node* bst_insert(Node* root, long long key) {
if (!root) return new Node(key);
if (key < root->value) root->left = bst_insert(root->left, key);
else if (key > root->value) root->right = bst_insert(root->right, key);
return root;
}