title: Sorting the elements in Binary trees
body: <p>Here is a question I was recently asked in an interview. A binary tree is given with a condition that each left child is 1 smaller than root and right child is 1 larger. Here is a sample tree </p>
  
  <p><a href="https://i.stack.imgur.com/Vj7n3.jpg" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/Vj7n3.jpg" alt="A tree"></a>               </p>
  
  <p>Sort it in O(1) and O(n) time complexity.</p>
  
  <p>Here are the approaches I suggested:</p>
  
  <ol>
  <li>Use a count to maintain the count of each elements and then return once entire traversal is done O(n) time and O(n) space complexity.</li>
  <li>Use run length encoding. Form a chain when the element is repeated with the number as the key and count as the value. Requires space for count only when no is repeated and so requires no extra space apart from array but the time complexity will be O(n log n) since we have to traverse the array to see if it is there.</li>
  <li>Finally I suggested breadth first traversal. We require O(log n) space for queue and O(n) time complexity (Assuming insertion is O(1) linked list).</li>
  </ol>
  
  <p>What are your approaches?</p>