191. In a min-heap with distinct keys, can a preorder, inorder or postorder traversal produce the keys in sorted order?
MediumPriority queues & heaps
Technical
Show model answer
Preorder visits a node before its children, and the heap property only promises that a parent is smaller than its children, so an ascending preorder is possible. Example: root 1, left child 2, right child 3 gives preorder 1 2 3. It is not guaranteed for every heap, only possible for some.
Inorder can never be sorted once a node has a left child: inorder lists that left child before its parent, yet the child is larger. So inorder is never ascending (n ≥ 2). Postorder lists the root (the minimum) last, so it can never be ascending, but it can be descending, for example root 1 with children 3 and 2 gives 3 2 1.
What interviewers listen for
- Preorder: ascending possible
- Inorder: never sorted for n ≥ 2
- Postorder: descending possible, ascending never