I came back to work on my basic binary tree implementation like a responsible adult. And like a child I started working on an unnecessary feature instead of a crucial one. Although I already built traversal functions I don’t have something that pretty prints the trees. I would really like that and I thought it would be a fun exercise to test my C programming skills. So far it’s like walking through deep snow with snow pants but the wrong pair of boots (slow, mildly irritating but eventually becomes frustrating).
TLDR;
Okay, so here are the highlights of what I did:
- Continued 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. I have started to build some tooling by adding an unnecessary but cool function that will use a Preorder Traversal and then pretty print the tree to the terminal/console (whatever it’s called LOL). I have not made a ton of progress but I think I can pull it off (I hope). My initial thought is to keep track of the level of the tree as the function is called recursively and store the values in an array of strings with each entity in the array representing an entire line of the tree that will be printed. Things might change but for now that all I have got. I will include my current code below. It’s messy to say the least.
Current Code with tons of comments LOL
/* Basic Tree Implementation in C
*
* Improvement 1: Improved Print function
*
* */
#include <stdio.h>
#include <stdlib.h>
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;
}
void printClean(treenode* root){
// Initialize container for each line of tree to print
// To dtermine the max size of each line of characters I need to
// know:
// - The number of branches each node has
// - The height of the tree
// - How many formatting characters do I need for each node value
// I need to print.
// Multiplying these three values will give us the maximum size
// of each character array(string) that represents each printed
// line of the tree.
//
int LINEPREFIX = 3;
char[][]* lines = malloc(sizeof());
// Print the tree as is in nice representation
if(root == NULL)
return;
printf("%i", root->value);
printNiceRec(root->left);
printNiceRec(root->right);
}
void printNiceRec(treenode* root){
// Print the tree as is in nice representation
if(root == NULL){
printf("%i\n", root->value);
}
}
void printInorder(treenode* root){
if(root->left != NULL){
printInorder(root->left);
}
printf("%i,", root->value);
if(root->right != NULL){
printInorder(root->right);
}
}
void printPreorder(treenode* root){
printf("%i,", root->value);
if(root->left != NULL){
printPreorder(root->left);
}
if(root->right != NULL){
printPreorder(root->right);
}
}
void printPostorder(treenode* root){
if(root->left != NULL){
printPostorder(root->left);
}
if(root->right != NULL){
printPostorder(root->right);
}
printf("%i,", root->value);
}
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
printf("--------------\n");
printf("Inorder Traversal: ");
printInorder(root);
printf("\n");
printf("Preorder Traversal: ");
printPreorder(root);
printf("\n");
printf("Postorder Traversal: ");
printPostorder(root);
printf("\n");
printf("--------------\n");
// Free all the memory once we are done. I am not sure why we are
// doing this but I am pretty sure C requires us to manage our own
// memory rather than having the compiler clean up after us.
// I think... I could be wrong about this.
free(root);
free(n2);
free(n3);
free(n4);
free(n5);
return 0;
}
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.