level-order traversal
Visiting a tree level by level from the root down, left to right within each level, using a queue.
In more detail
Dequeue a node, visit it and enqueue its children; the queue ensures nearer nodes come out first. It is breadth-first search applied to a tree, and the course uses it to print B-tree keys level by level.
Related terms
- tree traversal — Visiting every node of a tree exactly once in a systematic order.
- breadth-first search — A graph search that visits the start vertex, then all its neighbours, then all of theirs, spreading out in waves using a FIFO queue.
- queue — A collection where items leave in the order they arrived: first in, first out, like a line at a shop counter.
- deque — A double-ended queue: a sequence that adds and removes items at either end in O(1) time; Python provides it as collections.deque.
Taught in
- Stacks And Queues: Last In Or First In — Algorithms & Data Structures for Working Engineers
- Binary Trees And Their Traversals — Algorithms & Data Structures for Working Engineers
- B-Trees: The Structure Behind Every Database Index — Algorithms & Data Structures for Working Engineers
- Breadth-First Search And Shortest Paths By Hops — Algorithms & Data Structures for Working Engineers