Searching a Binary Search Tree
Nodes comparedlooking for 55
Nothing yet.
- Not reached
- On the stack
- Current
- Visited
1/3
Look for 55 in a balanced tree of 7 values, 3 levels deep.
Settings
More options
How it was built
Search
- 1
node = root - 2
while node: - 3
if target == node.value: return node - 4
if target < node.value: - 5
node = node.left - 6
else: - 7
node = node.right - 8
return NOT_FOUND
What Each Walk Is For
| Walk | What you get | Time | Extra space |
|---|---|---|---|
| In-Order | Values in sorted order | O(n) | O(h) |
| Pre-Order | Root before children, for copying a tree | O(n) | O(h) |
| Post-Order | Children before root, for freeing or evaluating | O(n) | O(h) |
| Level-Order | Shallowest nodes first, level by level | O(n) | O(w) |
| Search | One value, by comparing at each node | O(h) | O(1) |
Scroll the table sideways for the rest of the columns.
n is the number of values, h the height of the tree and w its widest level. Built from sorted values, the tree gets a height of n. Balanced trees exist to prevent that.