title: Print a tree in sorted order using heap properties (Cormen)
body: <p>I am refreshing on algorithm theory (from Cormen).<br>
  There is an exercise in the chapter for binary tries that asks:  </p>
  
  <blockquote>
    <p>Can the min-heap property be used to print out the keys of an n-node
    tree in sorted order in O(n) time? Show how, or explain why not.</p>
  </blockquote>
  
  <p>I thought yes it is possible.<br>
  In the min heap the element in a node is smaller than both its children.<br>
  So the root of the heap is always the smaller element of all the n elements and the left child of the root is the smaller than all the elements in the left subtree and the right child of the root is the smaller than all the elements in the right subtree etc.  </p>
  
  <p>So if keep we exracting the root, print it and then update the root with the smaller of its children we keep the min-heap property and we print in sorted order. (I am thinking of a min heap that is not array based).  </p>
  
  <p>So this could be done in O(n) time since to update the root, we just compare the 2 children and update the root's pointer to be the smaller of the 2.</p>
  
  <p>But I checked here in the solution:<br>
  <a href="http://mitpress.mit.edu/algorithms/solutions/chap12-solutions.pdf" rel="noreferrer">Cormen Supplement Solutions</a>  </p>
  
  <p>And 1)it talks about max-heaps 2) it says it can not be done in O(n) time:  </p>
  
  <blockquote>
    <p>In a heap, a node’s key is both of its children’s keys. In a binary
    search tree, a node’s key is its left child’s key, but its right
    child’s key. The heap property, unlike the binary-searth-tree
    property, doesn’t help print the nodes in sorted order because it
    doesn’t tell which subtree of a node contains the element to print
    before that node. In a heap, the largest element smaller than the node
    could be in either subtree. Note that if the heap property could be
    used to print the keys in sorted order in O(n) time, we would have an
    O(n)-time algorithm for sorting, because building the heap takes only
    O(n) time. But we know (Chapter 8) that a comparison sort must take
    (n lg n) time.</p>
  </blockquote>
  
  <p>From my point of view I can understand that using a max-heap, it is not possible to print them in O(n).<br>
  But isn't it possible to do it using the min-heap property for the reasoning I explained?<br>
  Also why does the solution ignore the min-heap. Is it a typo or error?  </p>
  
  <p>Am I misundertanding something here?  </p>