in-order traversal
Visiting a binary tree's left subtree, then the node itself, then its right subtree.
In more detail
On a binary search tree, in-order traversal produces the keys in ascending sorted order. That makes it a quick correctness check after inserts and deletes: if the output is not sorted, the tree is broken.
Related terms
- tree traversal — Visiting every node of a tree exactly once in a systematic order.
- binary search tree — A binary tree in which every key in a node's left subtree is smaller than the node's key and every key in its right subtree is larger.
Taught in
- Binary Trees And Their Traversals — Algorithms & Data Structures for Working Engineers
- Binary Search Trees: Search, Insert And Delete — Algorithms & Data Structures for Working Engineers