← DSA I

Binary search tree laboratory

BST Lab

0/8 traced

Insert

Descend to the correct null child, then attach the new leaf.

average case O(log n) time O(1) space
1Node* insert(Node* root, int k) {
2 if (root == nullptr) return newNode(k);
3 Node* cur = root; Node* parent = nullptr;
4 while (cur) { parent = cur;
5 cur = k < cur->value ? cur->left : cur->right; }
6 attach newNode(k) to parent as the correct child;
7 return root;
8}
currentT1
successor—
height2
nodes7
visited0
50 T1
30 T2
70 T3
20 T4
40 T5
60 T6
80 T7
RootCurrent Visited
Exact work through this line 2 +2 on this line
O(log n) time O(1) auxiliary space 0 peak visited nodes
0comparisons
0reads
0writes
1pointer reads
1pointer writes
0swaps
0allocations
0deallocations
0node visits
0iterations
0calls
0returns
Variables before line

currentnull

newNodenull

resultnull

nodesT1(50)→undefined · T2(30)→undefined · T3(70)→undefined · T4(20)→undefined · T5(40)→undefined · T6(60)→undefined · T7(80)→undefined

Variables after line

currentT1

newNodenull

resultnull

nodesT1(50)→undefined · T2(30)→undefined · T3(70)→undefined · T4(20)→undefined · T5(40)→undefined · T6(60)→undefined · T7(80)→undefined

Reads, writes, and state changes on this line

current.value null → T1 highlight

Why this bound?

O(log n) time · O(1) space

average
fixed readfixed writeInput may grow; this fixed-width work does not → 1
Auxiliary memory model
cursortemporarycounter

A bounded number of scalar/reference slots is reused, so auxiliary storage stays constant.

  1. Each comparison eliminates one subtree, moving down exactly one level.
  2. This tree has height 2 over 7 nodes — close to ⌈log₂(n+1)⌉.
  3. 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.
Step 1 of 12 · descend-init Start at root T1

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.

1 / 12