I’m trying to walk myself through printing the horizontal tree function. It has been a struggle but I have progressed to step two in my plan (hard code) the tree. I figure if I hard code it first I can review and find ways to make the code more dynamic. I just have to get something on the board. Mentally, I can’t wrap my head around the math behind producing an even layout. I think once I can see some real output and print, I will get closer to my goal. At least I hope so.
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 started playing around with some hard coded output and found some patterns. Once I find the consistent pattern I may be able to traverse the try. Insert the node values in their respective positions and output the formatted tree. Here’s hoping!!
- I read through chapter 1 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.
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:
/* 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??
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 prettyPrintVertRec(treenode* root, int level){
if(root == NULL) return;
prettyPrintVertRec(root->right, 1 + level);
for(int i = 0; i < level; ++i)
printf("\t");
printf("%i\n", root->value);
prettyPrintVertRec(root->left, 1 + level);
}
void prettyPrintVert(treenode* root){
if(root == NULL){
printf("Empty Tree\n");
return;
}
printf("--------------------\n\n");
prettyPrintVertRec(root->right, 1);
printf("%i\n", root->value);
prettyPrintVertRec(root->left, 1);
printf("\n--------------------");
}
void prettyPrintHoriz(treenode* root){
if(root == NULL){
printf("Empty Tree\n");
return;
}
int width = 24;
int height = calcHeight(root);
printf("\nHeight of tree: %i", height);
char treeDiagram[height+1][width];
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]);
}
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
// Testing Pretty Print Tree Vertically
prettyPrintVert(root);
prettyPrintHoriz(root);
//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;
}
And this is what I am producing from my code:
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.