title: Pretty-printing a binary tree in C (and other imperative languages)
body: <p>(<em>First-time poster and rather new in programming, so be patient, please!</em>)</p>
  
  <p>I'm interested in both an efficient general algorithm for printing formatted binary trees (in a CLI environment) and a <strong>C</strong> implementation. Here is some code that I wrote myself for fun (this is a much simplified version of the original and part of a larger program supporting many BST operations, but it should compile just fine):</p>
  
  <pre><code>#include &lt;stdbool.h&gt;    // C99, boolean type support
  #include &lt;stdio.h&gt;
  #include &lt;stdlib.h&gt;
  #include &lt;math.h&gt;
  
  #define DATATYPE_IS_DOUBLE
  #define NDEBUG                      // disable assertions
  #include &lt;assert.h&gt;
  
  #define WCHARBUF_LINES          20  // def: 20
  #define WCHARBUF_COLMS          800 // def: 80 (using a huge number, like 500, is a good idea,
                                      //          in order to prevent a buffer overflow :)
  #define RECOMMENDED_CONS_WIDTH  150
  #define RECOMMENDED_CONS_WIDTHQ "150"   // use the same value, quoted
  
  /* Preprocessor directives depending on DATATYPE_IS_* : */
  #if defined DATATYPE_IS_INT || defined DATATYPE_IS_LONG
      #define DTYPE           long int
      #define DTYPE_STRING    "INTEGER"
      #define DTYPE_PRINTF    "%*.*ld"
      #undef DATATYPE_IS_CHAR
  
  #elif defined DATATYPE_IS_FLOAT
      #define DTYPE           float
      #define DTYPE_STRING    "FLOAT"
      #define DTYPE_PRINTF    "%*.*f"
      #undef DATATYPE_IS_CHAR
  
  #elif defined DATATYPE_IS_DOUBLE
      #define DTYPE           double
      #define DTYPE_STRING    "DOUBLE"
      #define DTYPE_PRINTF    "%*.*lf"
      #undef DATATYPE_IS_CHAR
  
  #elif defined DATATYPE_IS_CHAR
      #define DTYPE           char
      #define DTYPE_STRING    "CHARACTER"
      #define DTYPE_PRINTF    "%*.*c" /* using the "precision" sub-specifier ( .* ) with a  */
                                      /* character will produce a harmless compiler warning */
  #else
      #error "DATATYPE_IS_* preprocessor directive undefined!"
  
  #endif
  
  
  typedef struct node_struct {
      DTYPE data;
      struct node_struct *left;
      struct node_struct *right;
      /* int height;  // useful for AVL trees */
  } node;
  
  typedef struct {
      node *root;
      bool IsAVL;     // useful for AVL trees
      long size;
  } tree;
  
  
  static inline
  DTYPE get_largest(node *n){
      if (n == NULL)
          return (DTYPE)0;
  
      for(; n-&gt;right != NULL; n=n-&gt;right);
  
      return n-&gt;data;
  }
  
  static
  int subtreeheight(node *ST){
      if (ST == NULL)
          return -1;
  
      int height_left  = subtreeheight(ST-&gt;left);
      int height_right = subtreeheight(ST-&gt;right);
  
      return (height_left &gt; height_right) ? (height_left + 1) : (height_right + 1);
  }
  
  
  void prettyprint_tree(tree *T){
      if (T == NULL)  // if T empty, abort
          return;
  
  #ifndef DATATYPE_IS_CHAR /* then DTYPE is a numeric type */
      /* compute spaces, find width: */
      int width, i, j;
      DTYPE max = get_largest(T-&gt;root);
  
      width = (max &lt; 10) ? 1 :
              (max &lt; 100) ? 2 :
              (max &lt; 1000) ? 3 :
              (max &lt; 10000) ? 4 :
              (max &lt; 100000) ? 5 :
              (max &lt; 1000000) ? 6 :
              (max &lt; 10000000) ? 7 :
              (max &lt; 100000000) ? 8 :
              (max &lt; 1000000000) ? 9 : 10;
      assert  (max &lt; 10000000000);
  
      width += 2; // needed for prettier results
  
  #if defined DATATYPE_IS_FLOAT || defined DATATYPE_IS_DOUBLE
      width += 2; // because of the decimals! (1 decimal is printed by default...)
  #endif // float or double
  
      int spacesafter = width / 2;
      int spacesbefore = spacesafter + 1;
      //int spacesbefore = ceil(width / 2.0);
  
  #else /* character input */
      int i, j, width = 3, spacesbefore = 2, spacesafter = 1;
  
  #endif // #ifndef DATATYPE_IS_CHAR
  
      /* start wchar_t printing, using a 2D character array with swprintf() : */
  
      struct columninfo{  // auxiliary structure
          bool visited;
          int  col;
      };
  
      wchar_t wcharbuf[WCHARBUF_LINES][WCHARBUF_COLMS];
      int line=0;
      struct columninfo eachline[WCHARBUF_LINES];
  
      for (i=0; i&lt;WCHARBUF_LINES; ++i){       // initialization
          for (j=0; j&lt;WCHARBUF_COLMS; ++j)
              wcharbuf[i][j] = (wchar_t)' ';
          eachline[i].visited = false;
          eachline[i].col = 0;
      }
  
      int height = subtreeheight(T-&gt;root);
  
      void recur_swprintf(node *ST, int cur_line, const wchar_t *nullstr){ // nested function,
                                                                              // GCC extension!
          float offset = width * pow(2, height - cur_line);
  
          ++cur_line;
  
          if (eachline[cur_line].visited == false) {
              eachline[cur_line].col = (int) (offset / 2);
              eachline[cur_line].visited = true;
          }
          else{
              eachline[cur_line].col += (int) offset;
              if (eachline[cur_line].col + width &gt; WCHARBUF_COLMS)
                  swprintf(wcharbuf[cur_line], L"  BUFFER OVERFLOW DETECTED! ");
          }
  
          if (ST == NULL){
              swprintf(wcharbuf[cur_line] + eachline[cur_line].col, L"%*.*s", 0, width, nullstr);
              if (cur_line &lt;= height){
                  /* use spaces instead of the nullstr for all the "children" of a NULL node */
                  recur_swprintf(NULL, cur_line, L"          ");
                  recur_swprintf(NULL, cur_line, L"          ");
              }
              else
                  return;
          }
          else{
              recur_swprintf(ST-&gt;left,  cur_line, nullstr);
              recur_swprintf(ST-&gt;right, cur_line, nullstr);
  
              swprintf(wcharbuf[cur_line] + eachline[cur_line].col - 1, L"("DTYPE_PRINTF"",
                       spacesbefore, 1, ST-&gt;data);
  
            //swprintf(wcharbuf[cur_line] + eachline[cur_line].col + spacesafter + 1, L")");
              swprintf(wcharbuf[cur_line] + eachline[cur_line].col + spacesafter + 2, L")");
          }
      }
  
      void call_recur(tree *tr){  // nested function, GCC extension! (wraps recur_swprintf())
          recur_swprintf(tr-&gt;root, -1, L"NULL");
      }
  
      call_recur(T);
  
      /* Omit empty columns: */
      int omit_cols(void){        // nested function, GCC extension!
          int col;
  
          for (col=0; col&lt;RECOMMENDED_CONS_WIDTH; ++col)
              for (line=0; line &lt;= height+1; ++line)
                  if (wcharbuf[line][col] != ' ' &amp;&amp; wcharbuf[line][col] != '\0')
                      return col;
  
          return 0;
      }
  
      /* Use fputwc to transfer the character array to the screen: */
      j = omit_cols() - 2;
      j = (j &lt; 0) ? 0 : j;
  
      for (line=0; line &lt;= height+1; ++line){     // assumes RECOMMENDED_CONS_WIDTH console window!
          fputwc('\n', stdout);                   // optional blanc line
          for (i=j; i&lt;j+RECOMMENDED_CONS_WIDTH &amp;&amp; i&lt;WCHARBUF_COLMS; ++i)
              fputwc(wcharbuf[line][i], stdout);
          fputwc('\n', stdout);
      }
  }
  </code></pre>
  
  <p>(<em>also uploaded to <a href="http://pastebin.ca/2027506" rel="nofollow noreferrer">a pastebin service</a>, in order to preserve syntax highlighting</em>)</p>
  
  <p>It works quite well, although the automatic width setting could be better. The preprocessor magic is a bit silly (or even ugly) and not really related to the algorithm, but it allows using various data types in the tree nodes (I saw it as a chance to experiment a bit with the preprocessor - remember, I am a newbie!).</p>
  
  <p>The main program is supposed to call</p>
  
  <pre>
  system("mode con:cols="RECOMMENDED_CONS_WIDTHQ" lines=2000");
  </pre>
  
  <p>before calling prettyprint_tree(), when running inside cmd.exe .</p>
  
  <p>Sample output:</p>
  
  <pre>
  
                                                    (106.0)
  
  
                        (102.0)                                                 (109.0)
  
  
          (101.5)                      NULL                       (107.0)                     (115.0)
  
  
    NULL          NULL                                     (106.1)        NULL         (113.0)        NULL
  
  
                                                        NULL   NULL                 NULL   NULL
  
  </pre>
  
  <p>Ideally, the output would be like this (the reason I'm using the wprintf() family of functions is being able to print Unicode characters anyway):</p>
  
  <pre>
              (107.0)
           ┌─────┴─────┐
       (106.1)        NULL
     ┌───┴───┐
    NULL   NULL
  </pre>
  
  <p>So, my questions:</p>
  
  <ul>
  <li>What do you think about this code? (Coding style suggestions are also very welcome!)</li>
  <li>Can it be extended in an elegant way in order to include the line-drawing characters? (Unfortunately, I don't think so.)</li>
  <li><strong>Any other algorithms in C or other imperative languages (or imperative pseudo-code)?</strong> </li>
  <li>Somewhat unrelated: What's your opinion about <strong>nested functions</strong> (non-portable GNU extension)? I think it's an elegant way to write recursive parts of a function without having to provide all the local variables as arguments (and also useful as an implementation-hiding technique), but it could be my Pascal past :-) I'm interested in the opinion of more experienced coders.</li>
  </ul>
  
  <p>Thank you in advance for your responses!</p>
  
  <p>PS. The question is <em>not</em> a duplicate of <a href="https://stackoverflow.com/questions/1733311">this one</a>.</p>
  
  <hr>
  
  <p><strong>edit:</strong>
  <a href="https://stackoverflow.com/users/15168/jonathan-leffler">Jonathan Leffler</a> wrote an <a href="https://stackoverflow.com/questions/4522281/4523754#4523754">excellent answer</a> that will most probably become the "accepted answer" after a few days (unless someone posts something equally awesome!). I decided to respond here instead of commenting because of the space constraints.</p>
  
  <ul>
  <li>The code above is actually part of a larger "homework" project (implementing BST operations in a shared library + a CLI app using that library). However, the "prettyprint" function was <strong>not</strong> part of the requirements; just something I decided to add myself.</li>
  <li>I also added a "convert to AVL without rotations" function, that used "arraystr" as an intermediate representation ;-) I forgot that it wasn't used here. I've edited the code to remove it. Also, the <code>bool IsAVL</code> struct member is anything but unused; just not used in this particular function. I had to copy/paste code from various files and make a lot of changes in order to present the code cited above. That's a problem that I don't know how to solve. I would gladly post the whole program, but it is too large and commented in my mother-tongue (not in English!).</li>
  <li>The whole project was about 1600 LOC (including comments) with multiple build targets (debug/release/static-linking) and it compiled <strong>cleanly</strong> with <code>-Wall</code> and <code>-Wextra</code> enabled. Assertions and debug messages were enabled/disabled automatically depending on the build target. Also I thought that function prototypes weren't needed for nested functions, after all nested functions do not implement any external interface <em>by definition</em> - GCC certainly didn't complain here. I don't know why there are so many warnings on OSX :(</li>
  <li>I'm using GCC 4.4.1 on Windows 7.</li>
  <li>Despite writing and testing this program on Windows, I am actually a Linux user... Still, I can't stand <code>vim</code> and I use <code>nano</code> (inside GNU screen) or <code>gedit</code> instead (shoot me)!  In any case, I prefer the K&amp;R brace style :)</li>
  <li>Portability doesn't really matter, for Linux users GCC is pretty much <em>de facto</em>... The fact that it also works well under Windows is a nice bonus.</li>
  <li>I'm not using a VCS, perhaps I should. I want to try, but all of them seem too complex for my needs and I don't know how to choose one :-)</li>
  <li>You are definitely right about checking for depth overflow, thankfully it is very easy to add.</li>
  <li>Thanks for the <code>L' '</code> advice!</li>
  <li>I find your suggestion (encapsulating <em>"the whole of the drawing code so that the screen image and related information is in a single structure"</em>) <strong>extremely</strong> interesting... but I don't really understand what you mean as "encapsulation". Could you, please, provide 3 or 4 lines of (pseudo)code showing a possible function declaration and/or a possible function call?</li>
  </ul>
  
  <p>This is my first "large-ish" (and non-trivial) program and I'm really thankful for your advice.</p>
  
  <hr>
  
  <p><strong>edit #2:</strong>
  Here is an implementation of the "quick and dirty" method mentioned <a href="https://stackoverflow.com/questions/4522281/4525182#4525182">here</a>.<br>
  (<strong>edit #3:</strong> I decided to split it to a <a href="https://stackoverflow.com/questions/4522281/4528909#4528909">separate answer</a>, since it is a valid answer to the OP.)</p>
  
  <p>Many responses mentioned <a href="http://www.graphviz.org/" rel="nofollow noreferrer">Graphviz</a>. I already knew about it (many Linux apps are linked against it) but I thought it would be overkill for a 10KB CLI executable. However, I'll keep it in mind for the future. It seems great.</p>