title: Printing in-reverse-order AVL tree
body: <p>I'm building an AVL tree, and trying to print it in reverse order (descending). I don't wish to change my <code>insert</code> function because I also use classic in-order printing sometimes. So, what I thought was -> I need to swap access to <code>right</code> and <code>left</code> nodes and it would be printed in reverse.</p>
  
  <pre><code>void inOrder(struct node *root)
  {
      if(root != NULL)
      {
        inOrder(root-&gt;left);
        printf("%lf\n", root-&gt;key);
        inOrder(root-&gt;right);
      }
  }
  
  void inOrderDecreasing(struct node *root)
  {
      if(root != NULL)
      {
        inOrder(root-&gt;right);
        printf("%lf\n", root-&gt;key);
        inOrder(root-&gt;left);
      }
  }
  </code></pre>
  
  <p>However, this doesn't work. <code>inOrder</code> works as it should, but the other function does not.</p>
  
  <p>What I get:</p>
  
  <pre><code>45.943100
  78.321899
  99.200996
  32.750999
  10.475900
  25.170500
  </code></pre>
  
  <p>In case someone wants to check out my insert function:</p>
  
  <pre><code>// A utility function to right rotate subtree rooted with y
  // See the diagram given above.
  struct node *rightRotate(struct node *y)
  {
      struct node *x = y-&gt;left;
      struct node *T2 = x-&gt;right;
  
      // Perform rotation
      x-&gt;right = y;
      y-&gt;left = T2;
  
      // Update heights
      y-&gt;height = max(height(y-&gt;left), height(y-&gt;right))+1;
      x-&gt;height = max(height(x-&gt;left), height(x-&gt;right))+1;
  
      // Return new root
      return x;
  }
  
  // A utility function to left rotate subtree rooted with x
  // See the diagram given above.
  struct node *leftRotate(struct node *x)
  {
      struct node *y = x-&gt;right;
      struct node *T2 = y-&gt;left;
  
      // Perform rotation
      y-&gt;left = x;
      x-&gt;right = T2;
  
      //  Update heights
      x-&gt;height = max(height(x-&gt;left), height(x-&gt;right))+1;
      y-&gt;height = max(height(y-&gt;left), height(y-&gt;right))+1;
  
      // Return new root
      return y;
  }
  
  /*
   * RECAP Balance is based on Height
   *     Hn = Hl - Hr
   * so
   *    positive =&gt; LEFT HEAVY
   *    negative =&gt; RIGHT HEAVY
   */
  // Get Balance factor of node N
  int getBalance(struct node *N)
  {
      if (N == NULL)
          return 0;
      return height(N-&gt;left) - height(N-&gt;right);
  }
  
  struct node* insert(struct node* node, float key)
  {
      /* 1.  Perform the normal BST insertion */
      if (node == NULL)
          return(newNode(key));
  
      if (key &lt; node-&gt;key)
          node-&gt;left  = insert(node-&gt;left, key);
      else
          node-&gt;right = insert(node-&gt;right, key);
  
      /* 2. Update height of this ancestor node */
      node-&gt;height = max(height(node-&gt;left), height(node-&gt;right)) + 1;
  
      /* 3. Get the balance factor of this ancestor node to check whether
         this node became unbalanced */
      int balance = getBalance(node);
  
      // If this node becomes UNBALANCED, then there are 4 cases
  
      /* CASE # 1 =&gt; LEFT-LEFT aka left?
         T1, T2, T3 and T4 are subtrees.
           z                                      y
          / \                                   /   \
         y   T4      Right Rotate (z)          x      z
        / \          - - - - - - - - -&gt;      /  \    /  \
       x   T3                               T1  T2  T3  T4
      / \
    T1   T2
       */
      // Left Left Case in code
      if (balance &gt; 1 &amp;&amp; key &lt; node-&gt;left-&gt;key)
          return rightRotate(node);
  
      /* Case #2 =&gt; RIGHT-RIGHT aka right?
  
         z                                y
        /  \                            /   \
       T1   y     Left Rotate(z)       z      x
           / \   - - - - - - - --&gt;    / \    / \
      T2  x                     T1  T2 T3  T4
         / \
       T3  T4
  
       */
      // Right Right Case in code
      if (balance &lt; -1 &amp;&amp; key &gt; node-&gt;right-&gt;key)
          return leftRotate(node);
  
  
      /* CASE # 3 =&gt; LEFT-RIGHT aka left-right?
       z                               z                           x
      / \                            /   \                        /  \
     y   T4  Left Rotate (y)        x    T4  Right Rotate(z)    y      z
    / \      - - - - - - - - -&gt;    /  \      - - - - - - - -&gt;  / \    / \
  T1   x                          y    T3                    T1  T2 T3  T4
      / \                        / \
    T2   T3                    T1   T2
  
      */
      // Left Right Case in code
      if (balance &gt; 1 &amp;&amp; key &gt; node-&gt;left-&gt;key)
      {
          node-&gt;left =  leftRotate(node-&gt;left);
          return rightRotate(node);
      }
      /* CASE #4 = RIGHT-LEFT aka right-left?
          z                            z                            x
         / \                          / \                          /  \
        T1   y   Right Rotate (y)    T1   x      Left Rotate(z)   z      y
        / \   - - - - - - - - -&gt;     /  \      - - - - - - - -&gt;  / \    / \
      x   T4                       T2    y                      T1  T2  T3  T4
     / \                                /  \
   T2   T3                             T3   T4
       */
      // Right Left Case in code
      if (balance &lt; -1 &amp;&amp; key &lt; node-&gt;right-&gt;key)
      {
          node-&gt;right = rightRotate(node-&gt;right);
          return leftRotate(node);
      }
  
      /* return the (unchanged) node pointer */
      return node;
  }
  </code></pre>