• 1

• 35.2k
• 13
• 134
• 238

Improvements on C coding style Binary tree encoding

• 1.1k
• 8
• 22

I implemented a solution to this coding challenge on the CodeGolf stackexchange (should be open for public beta anytime now). I have decent experience with C/C++, but it's been a while since I've used them extensively.

I've included the source code here for convenience.

#include <math.h>
#include <stdio.h>
#include <stdlib.h>
// Prototypes
struct BTnode;
struct BTnode * bt_add_left(struct BTnode * node, int data);
struct BTnode * bt_add_right(struct BTnode * node, int data);
int bt_depth(struct BTnode * tree);
int bt_encode_preorder(int * list, struct BTnode * tree, int index);
struct BTnode * bt_node_create(int data);
int bt_node_delete(struct BTnode * node);
void bt_print_preorder(struct BTnode * tree);
int * encode(struct BTnode * tree);
struct BTnode * decode(int * list);
// Binary tree node
struct BTnode
{
 int data;
 struct BTnode *left, *right;
};
// Add node to this node's left
struct BTnode * bt_add_left(struct BTnode * node, int data)
{
 struct BTnode * newnode = bt_node_create(data);
 node->left = newnode;
 return newnode;
}
// Add node to this node's right
struct BTnode * bt_add_right(struct BTnode * node, int data)
{
 struct BTnode * newnode = bt_node_create(data);
 node->right = newnode;
 return newnode;
}
// Determine depth of the tree
int bt_depth(struct BTnode * tree)
{
 int depth;
 int leftdepth = 0;
 int rightdepth = 0;
 if( tree == NULL ) return 0;
 if( tree->left != NULL )
 leftdepth = bt_depth(tree->left);
 if( tree->right != NULL )
 rightdepth = bt_depth(tree->right);
 depth = leftdepth;
 if(rightdepth > leftdepth)
 depth = rightdepth;
 return depth + 1;
}
// Recursively add node values to integer list, using 0 as an unfolding sentinel
int bt_encode_preorder(int * list, struct BTnode * tree, int index)
{
 list[ index++ ] = tree->data;
 
 // This assumes the tree is complete (i.e., if the current node does not have
 // a left child, then it does not have a right child either)
 if( tree->left != NULL )
 {
 index = bt_encode_preorder(list, tree->left, index);
 index = bt_encode_preorder(list, tree->right, index);
 }
 // Add sentinel
 list[ index++ ] = 0;
 return index;
}
// Allocate memory for a node
struct BTnode * bt_node_create(int data)
{
 struct BTnode * newnode = (struct BTnode *) malloc(sizeof(struct BTnode));
 newnode->left = NULL;
 newnode->right = NULL;
 newnode->data = data;
 return newnode;
}
// Free node memory
int bt_node_delete(struct BTnode * node)
{
 int data;
 if(node == NULL)
 return 0;
 data = node->data;
 
 if(node->left != NULL)
 bt_node_delete(node->left);
 if(node->right != NULL)
 bt_node_delete(node->right);
 
 free(node);
 return data;
}
// Print all values from the tree in pre-order
void bt_print_preorder(struct BTnode * tree)
{
 printf("%d ", tree->data);
 if(tree->left != NULL)
 bt_print_preorder(tree->left);
 if(tree->right != NULL)
 bt_print_preorder(tree->right);
}
// Decode binary tree structure from a list of integers
struct BTnode * decode(int * list)
{
 struct BTnode * tree;
 struct BTnode * nodestack[ list[0] ];
 int i,j;
 // Handle trivial case
 if( list == NULL ) return NULL;
 tree = bt_node_create( list[1] );
 nodestack[ 1 ] = tree;
 j = 1;
 for(i = 2; i < list[0]; i++)
 {
 if( list[i] == 0 )
 {
 //printf("popping\n");
 j--;
 }
 else
 {
 if( nodestack[j]->left == NULL )
 {
 //printf("Adding %d to left of %d\n", list[i], nodestack[j]->data);
 nodestack[ j+1 ] = bt_add_left(nodestack[j], list[i]);
 j++;
 }
 else
 {
 //printf("Adding %d to right of %d\n", list[i], nodestack[j]->data);
 nodestack[ j+1 ] = bt_add_right(nodestack[j], list[i]);
 j++;
 }
 }
 }
 return tree;
}
// Encode binary tree structure as a list of integers
int * encode(struct BTnode * tree)
{
 int maxnodes, depth, length;
 int * list;
 int j;
 // Handle trivial case
 if(tree == NULL) return NULL;
 
 // Calculate maximum number of nodes in the tree from the tree depth
 maxnodes = 1;
 depth = bt_depth(tree);
 for(j = 0; j < depth; j++)
 {
 maxnodes += pow(2, j);
 }
 // Allocate memory for the list; we need two ints for each value plus the
 // first value in the list to indicate length
 list = (int *) malloc( ((maxnodes * 2)+1) * sizeof(int));
 length = bt_encode_preorder(list, tree, 1);
 list[ 0 ] = length;
 return list;
}
int main()
{
 struct BTnode * tree;
 struct BTnode * newtree;
 int * list;
 int i;
 /* Provided example
 
 5
 / \
 3 2
 / \
 2 1
 / \
 9 9
 */
 tree = bt_node_create(5);
 bt_add_left(tree, 3);
 struct BTnode * temp = bt_add_right(tree, 2);
 bt_add_right(temp, 1);
 temp = bt_add_left(temp, 2);
 bt_add_left(temp, 9);
 bt_add_right(temp, 9);
 printf("T (traversed in pre-order): ");
 bt_print_preorder(tree);
 printf("\n");
 list = encode(tree);
 printf("T (encoded as integer list): ");
 for(i = 1; i < list[0]; i++)
 printf("%d ", list[i]);
 printf("\n");
 newtree = decode(list);
 printf("T' (decoded from int list): ");
 bt_print_preorder(newtree);
 printf("\n\n");
 // Free memory
 bt_node_delete(tree);
 bt_node_delete(newtree);
 free(list);
 return 0;
}

How could my program be improved? I'm thinking mostly in terms of clarity/readability, maintainablity, and reusability, but I also welcome any comments about my implementation of the data structures and any possible improvements in terms of performance or correctness. Thanks!