I tried to implement my own functions for traversing and printing out the values of a tree using Inorder, Preorder, and Postorder Tree Traversal respectively. Plus I did it without looking at some example code first. I felt pretty proud about that since up until now I have relied on example code because of my lack of confidence tackling new ideas on top of a new programming language. Hopefully this is a good sign for me.

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. I continued my work on Tree data structures. I started writing an implementation of a binary tree data structure in C I am doing so by following a YouTube Video. Started on writing the print tree function when I realized that I do not fully understand the differences between the types of tree traversals that can be used in a print function. I went back to my notes and found an decent article to read on the topic. I successfully implemented the print functions for the three different tree traversals mentioned in the article. I have not checked out their examples yet but I plan to do so tomorrow before moving on with the tutorial video I found on YouTube.

Traversing a Tree

Trees can be traversed in multiple ways. Whereas linked lists, arrays, stacks, and many other data structures can only be traversed in a forwards or backwards order. Trees have 3 main types of traversals. “Inorder”, “Preorder”, and “Postorder” Traversals. There are also “Breadth-First” or “Level Order” Traversals. If we take a simple tree as an example, we can highlight the differences between the different types of traversals:

    1
   / \
  2   3
 / \
4   5

• Inorder Traversal (left, root, right) = 4,2,5,1,3
• Preorder Traversal (root, left, right) = 1,2,4,5,3
• Postorder Traversal (Left, Right, Root) = 4,5,2,3,1
• Breadth-First or Level Order Traversal = 1,2,3,4,5

Example Code

/* Basic Tree Implementation in C
 *
 * */

#include <stdio.h>
#include <stdlib.h>

// Ironically although all nodes except root have one edge we are 
// constructing our nodes to have edges for children instead of an 
// edge associated with our parents. It feels more natural this way
// although I wonder if there is a benefit to constructing our node
// to have only a pointer to it's parent and build the tree that way
// .
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 printtree(treenode* root){
//   if(root == NULL){
//     printf("---<empty>---\n");
//     return;
//   }
// }

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.