AlgoScope

Binary Search Tree

Smaller values sit left, larger sit right, so a search walks one path down.

Data structures, data structure, beginnerAlso called BST
Comparing 45 with node 50. 45 is smaller, so move to the left child, node 30.203035404550607080current50 > 45

Binary Search Tree: Search for 45

Decision, step 2 of 6

45 is smaller than 50: go left.

Cost

Search
O(h)
Insert
O(h)
Delete
O(h)
Space
O(n)

h is the height. O(log n) when balanced O(n) when degenerate.

Leads to

Topics that need this one first.

Taught by the same lesson

Binary Search Tree covers these too, in the same run.