Step 3 of 6

Traversals and validation

Three classic depth-first orders visit every node:

• pre-order: node, left, right (copying a tree, serializing it)
• in-order: left, node, right (a BST comes out sorted)
• post-order: left, right, node (deleting a tree, evaluating an expression tree)

In-order gives a neat BST check, but there's a subtler direct one: every node must lie within a range inherited from its ancestors. Checking only that each child is on the correct side of its parent is a classic wrong answer: a node can be right of its parent but still too big for its grandparent.

Your turn: write void in_order(const Node* n, std::vector<int>& out) and bool is_bst(const Node* n, long lo, long hi) that checks all keys lie strictly between lo and hi (the test calls it with LONG_MIN, LONG_MAX).

Previous: Binary search trees Next: Level order with a queue