I worked on getting the filler 0 value pretty printed for all the node positions in a tree. It sort of worked. The spacing isn’t working the way it should but at least I have a consistent way to distribute nodes at each level. Again, a geometric progression seems to be the best method for producing a consistent patterns at each level of the tree. I think once I get the spacing working, I can perform an Inorder traversal on the tree to get the values and store them in an array. Only this time, whenever a node pointer is NULL I give a null value to the collection array?? Still have not got that far so my ideas might change.

TLDR;

Okay, so here are the highlights of what I did:

• Continued to work on the “Technical Questions” section of the book “Cracking the Coding Interview” by Gayle Laakmann McDowell. Within that, I continued my work on Tree data structures. Started trying to replicate the example pretty print functions provided in the article I am reading through. I am still trying to replicate the horizontal pretty print that was introduced in the article. I added some code to produce a filler value (0) for each node that could potentially exist at each level of the tree. My spacing in-between the nodes was less than desirable though. I need to work on that.
• I read through half of chapter 3 of “Eloquent JavaScript” by Marjin Haverbeke. I am starting to read the book to help cover some insecurities I have about my knowledge of the language. I learned JavaScript on the fly through projects and YouTube videos. There are some core questions about the language that I don’t think I can answer, so hopefully this will help. I spent a lot of time on the sections on scoping variables, and closures. I will likely review it again tomorrow before moving on since this is one of the core topics I starting reading this book to hopefully better familiarize myself with.

Reference Article

I am reading through this article’s example “Pretty Print” for a tree. Thankfully they have multiple forms that I can learn from.

Horizontal Output Example

                                 1

                2                                3

        4                5                6                7

    8        9        10        11        12        13        14        15

So far this is my code (relevant functions only to keep it cleaner looking):

/* Basic Tree Implementation in C
 *
 * Improvement 1.2: Horizontal Pretty Print
 * Step 1: Get comfortable with the C language features for task
 * Step 2: Build a hard coded version of the desired output
 * Step 3: Start making aspects of the code dynamic
 *
 * */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>    // Include string manipulation library??
#include <math.h>      // Include math manipulation library??

typedef struct treenode {
  int value;
  struct treenode* left;
  struct treenode* right;
} treenode;

treenode* createNode(int value){
  treenode* result = malloc(sizeof(treenode));
  if(result != NULL){
    result->value = value;
    result->left = NULL;
    result->right = NULL;
  }
  return result;
}

int calcHeight(treenode* node){
  int leftHeight = 0, rightHeight = 0;

  if(node == NULL)
    return 0;

  if(node->left != NULL)
    leftHeight = 1 + calcHeight(node->left);

  if(node->right != NULL)
    rightHeight = 1 + calcHeight(node->right);

  return leftHeight >= rightHeight ? leftHeight : rightHeight;
}

void printSpace(int multiple, int spaceValue, bool inbetween){
  int numSpaces = (int) pow(2, multiple) * spaceValue;
  int spacesToUse = inbetween ? (numSpaces - 1) : numSpaces;
  for(int i=0; i < spacesToUse; ++i)
    printf(" ");
}

void prettyPrintHoriz(treenode* root){
  if(root == NULL){
    printf("Empty Tree\n");
    return;
  }
  int width = 24;
  int height = calcHeight(root);
  const int SPACE = 3;

  char treeDiagram[height+1][width];

  printf("\n");
  for(int i = 0; i < (height+1); ++i){
    // Print the intial space to align the next level
    printSpace(height - i, SPACE, false);
    int numNodes = (int) pow(2,i);
    for(int j = 0; j < numNodes; ++j ){
      printf("0");
      if(j>0) printSpace(height - i, SPACE, true);
    }
    printf("\n\n");
  }

  strcpy(treeDiagram[0], "            1\n");
  strcpy(treeDiagram[1], "      2           3\n");
  strcpy(treeDiagram[2], "   4     5\n");

  for(int i = 0; i < height+1; ++i)
    printf("\n%s", treeDiagram[i]);
}


int main(){
  treenode* root = createNode(1);
  treenode* n2 = createNode(2);
  treenode* n3 = createNode(3);
  treenode* n4 = createNode(4);
  treenode* n5 = createNode(5);

  root->left = n2;
  root->right = n3;
  n2->left = n4;
  n2->right = n5;
  // Structure of current tree:
  //
  //       root
  //      /    \
  //    n2      n3
  //           /  \
  //         n4    n5

  //      1
  //     / \
  //    2   3
  //   / \
  //  4   5

  // Testing Horizontal Pretty Print
  prettyPrintHoriz(root);

  // Free memory
  free(root);
  free(n2);
  free(n3);
  free(n4);
  free(n5);

  return 0;
}

And this is what I am producing from my code:

            0

      00

   00  0  0


            1

      2           3

   4     5

Conclusion

That’s all for today. This is my sixth round of the “#100daysofcode” challenge. I will be continuing my work from round five into round six. I am currently working through the book “Cracking the Coding Interview” by Gayle Laakmann McDowell. My goal is to become more familiar with algorithms and data structures. This goal was derived from my goal to better understand operating systems and key programs that I use in the terminal regularly e.g. Git. This goal was in term derived from my desire to better understand the fundamental tools used for coding outside of popular GUIs. This in turn was derived from my desire to be a better back-end developer.

I have no idea if my path is correct but I am walking down this road anyways. Worst case scenario I learn a whole bunch of stuff that will help me out on my own personal projects.