After all this hard work I can now pretty print a fake tree (still haven’t wrote the tree data pulling code). It took a bit of digging but I found the mistakes in my code and now all that’s left is to perform an Inorder traversal that will return the value in the tree or a blank marker so that at each position in the tree I can print something. I still have a bit left to go but it has been a great trip so far. I feel ready to move on and build the other tools for a tree data structure.
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 fixed some code to produce a filler value (
0) for each node that could potentially exist at each level of the tree. Now my spacing in-between nodes is working fine. The tree looks pretty good not gonna lie! - I read through the other half of chapter 3, and half of chapter 4 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. Chapter 4 has finally introduced references and JavaScript objects. So far so good but the code complexity is definitely starting to ramp up. I am here for it!!!
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){
int numSpaces = (int) pow(2, multiple) * spaceValue;
for(int i=0; i < numSpaces; ++i)
printf(" ");
}
void printSpaceInbetween(int multiple, int spaceValue){
int numSpaces = (int) pow(2, multiple) * spaceValue;
// equal spacing formula for single digit node values
int spacesToUse = ((numSpaces - 1) * 2) + 1;
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);
int numNodes = (int) pow(2,i);
for(int j = 0; j < numNodes; ++j ){
if(j>0) printSpaceInbetween(height - i, SPACE);
printf("0");
}
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
0 0
0 0 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.