An in-order traversal of a binary search tree results the elements of an n node tree in sorted order in O(n) time. Can heap do the same?
While in-order traversal heap will not sort the elements. Heap property states that the left child and right child of a node (n) contains elements lesser (or greater for min heap) than itself. If we perform in-order traversal on heap, it will print the element lesser than n first - left child, then n, and then the right child (but in this case the right child is less than n). So the elements are not printed in sorted order. |