title: Max-Heapify A Binary Tree
body: <p>This is one of the interview questions I recently came across. </p>
  
  <p>Given the root address of a complete or almost complete binary tree, we have to write a function to convert the tree to a max-heap. </p>
  
  <p>There are no arrays involved here. The tree is already constructed.</p>
  
  <p>For e.g., </p>
  
  <pre><code>              1   
           /         \
          2           5
        /   \       /   \ 
       3      4    6     7
  </code></pre>
  
  <p>can have any of the possible max heaps as the output--</p>
  
  <pre><code>              7   
           /         \
          3           6
        /   \       /   \ 
       2     1     4     5
  </code></pre>
  
  <p>or</p>
  
  <pre><code>              7   
           /         \
          4           6
        /   \       /   \ 
       2     3     1     5
  </code></pre>
  
  <p>etc...</p>
  
  <p>I wrote a solution but using a combination of pre and post order traversals but that I guess runs in O(n^2). My code gives the following output.</p>
  
  <pre><code>              7   
           /         \
          3           6
        /   \       /   \ 
       1     2     4     5
  </code></pre>
  
  <p>I was looking for a better solution. Can somebody please help?</p>
  
  <p>Edit :</p>
  
  <h2>My Code</h2>
  
  <pre><code>void preorder(struct node* root)
  {    
      if(root==NULL)return;
      max_heapify(root,NULL);
      preorder(root-&gt;left); 
      preorder(root-&gt;right);
  }
  void max_heapify(struct node* root,struct node* prev)
  {
      if(root==NULL)
          return ;             
      max_heapify(root-&gt;left,root);
      max_heapify(root-&gt;right,root);
      if(prev!=NULL &amp;&amp; root-&gt;data &gt; prev-&gt;data)
      {
          swapper(root,prev);
      }     
  }
  void swapper(struct node* node1, struct node* node2)
  {   
      int temp= node1-&gt;data;
      node1-&gt;data = node2-&gt;data;
      node2-&gt;data = temp;
  }
  </code></pre>