Level-Order Traversal (Breadth-First on a Tree)
Output so far
Nothing yet.
- Not reached
- On the stack
- Current
- Visited
1/13
Level-Order walk over 7 values, 3 levels deep.
Settings
More options
How it was built
Level-Order
- 1
queue = [root] - 2
while queue: - 3
node = queue.shift() - 4
visit(node) - 5
enqueue node.left - 6
enqueue node.right
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.