Insert
Descend to the correct null child, then attach the new leaf.
1Node* insert(Node* root, int k) {2if (root == nullptr) return newNode(k);3Node* cur = root; Node* parent = nullptr;4while (cur) { parent = cur;5cur = k < cur->value ? cur->left : cur->right; }6attach newNode(k) to parent as the correct child;7return root;8}
T1—270currentnull
newNodenull
resultnull
nodesT1(50)→undefined · T2(30)→undefined · T3(70)→undefined · T4(20)→undefined · T5(40)→undefined · T6(60)→undefined · T7(80)→undefined
currentT1
newNodenull
resultnull
nodesT1(50)→undefined · T2(30)→undefined · T3(70)→undefined · T4(20)→undefined · T5(40)→undefined · T6(60)→undefined · T7(80)→undefined
current.value null → T1 highlight
O(log n) time · O(1) space
averageA bounded number of scalar/reference slots is reused, so auxiliary storage stays constant.
- Each comparison eliminates one subtree, moving down exactly one level.
- This tree has height 2 over 7 nodes — close to ⌈log₂(n+1)⌉.
- One comparison per level is O(log n) time; two pointers are O(1) auxiliary space.
Assumptions behind this claim
- Keys are distinct, so the BST ordering is unambiguous.
- Complexity depends on the tree shape produced by the insertion order.
- Insertion order kept the tree bushy.
- Each displayed comparison, pointer move, visit, or push/pop is one counted primitive.
- Trace construction and visualization bookkeeping are excluded from the algorithm count.
BST descent never scans the whole tree — only one root-to-leaf path.
About this implementation
A BST search discards a whole subtree per comparison, so a balanced tree is O(log n) — but the tree is built from the order you type, and a sorted order chains it into an O(n) list. Deleting a two-child node promotes its in-order successor. DFS traversals use O(h) call-stack space; level-order BFS uses O(w) queue space; height is a postorder computation over every node.