tree traversal
Visiting every node of a tree exactly once in a systematic order.
In more detail
The four standard orders are in-order, pre-order, post-order and level-order. All take O(n) time; the recursive ones use O(h) stack space and level-order uses a queue. Which order to use depends on whether parents must come before, between or after their children.
Related terms
- in-order traversal — Visiting a binary tree's left subtree, then the node itself, then its right subtree.
- pre-order traversal — Visiting a node first, then its left subtree, then its right subtree.
- post-order traversal — Visiting a node's left subtree, then its right subtree, and the node itself last.
- level-order traversal — Visiting a tree level by level from the root down, left to right within each level, using a queue.
Taught in
- Arrays: Contiguous Memory And Constant-Time Access — Algorithms & Data Structures for Working Engineers
- Linked Lists: Nodes, Pointers And Sentinels — Algorithms & Data Structures for Working Engineers
- Stacks And Queues: Last In Or First In — Algorithms & Data Structures for Working Engineers
- Choosing The Right Sequence — Algorithms & Data Structures for Working Engineers
- Binary Trees And Their Traversals — Algorithms & Data Structures for Working Engineers
- Representing A Graph: Matrix Or Adjacency List — Algorithms & Data Structures for Working Engineers