Skip to interview prep
Apexed

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
In a min-heap with distinct keys, can a preorder, inorder or postorder traversal produce the keys in sorted order — Data structures & algorithms interview quest