In-Order Traversal

overview

Summary

An in_order_traversal visits a binary_tree in left_root_right order: left subtree, node, right subtree. It is a depth_first strategy. On a binary_search_tree it outputs keys in sorted order. Common ways: recursion or an explicit stack_based loop; both run in time_o(n). Typical extra space is space_o(h), where h is height. A third option, morris_traversal, achieves space_o(1) by temporary threading. Remember: process left, then node, then right, and expect sorted results for BSTs.