# Binary tree encoding

I implemented a solution to this coding challenge on the Code Golf. I have decent experience with C/C++, but it's been a while since I've used them extensively.

#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);
}

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);
struct BTnode * temp = bt_add_right(tree, 2);
temp = bt_add_left(temp, 2);
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, maintainability, 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.

### In int bt_depth(struct BTnode * tree)

Too many different checks for NULL.
You only need to check once. The call to bt_depth() on the left and right nodes will perform there own explicit checks don't try and pre optimize.

int bt_depth(struct BTnode * tree)
{
if( tree == NULL ) return 0;
int leftdepth  = bt_depth(tree->left);
int rightdepth = bt_depth(tree->right);

return max(leftdepth, rightdepth) + 1;
}


### In int bt_encode_preorder(int * list, struct BTnode * tree, int index)

You are using tree without check for NULL tree

list[ index++ ] = tree->data;


You are also doing a recursive call without checking.
At some point you may end up hitting a NULL and trying to de-reference it.

if( tree->left != NULL )
{
index = bt_encode_preorder(list, tree->left, index);
index = bt_encode_preorder(list, tree->right, index); // tree->right may be NULL!!!!
}


### In int bt_node_delete(struct BTnode * node)

This is note a node delete this is a full tree delete.
It should be named appropriately.

### In void bt_print_preorder(struct BTnode * tree)

It is easier just to check if the current node is NULL.
The always print left and right nodes.

void bt_print_preorder(struct BTnode * tree)
{
if (tree == NULL) return;

printf("%d ", tree->data);
bt_print_preorder(tree->left);
bt_print_preorder(tree->right);
}


### In encode(struct BTnode * tree)

  // 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);
}


This is the only use of bt_depth(). Rather than do this why not just have a function called bt_count_nodes(BTnode* tree) that actual counts the nodes (bt_depth actually traverses all the nodes anyway (why not count them instead of the depth).

### In struct BTnode * decode(int * list)

I can quite work out if this is correct without running it. This is a bad sign that the code could do with simplification.

• Loki pointed out redundant NULL-checks in bt_depth; the same redundant checks also appear in bt_node_delete. – Quuxplusone Sep 12 '12 at 22:06

I only have a minute before running out the door, so here's the first thing I saw:

• Its good practice to set your pointers to NULL after you free them. Just as you are testing to ensure its not set to NULL since you do that upon creation, you should do that when deleting.
• It's considered good practice in some circles to set pointers to NULL after freeing them. But in other equally valid circles, it's considered bad practice to assign anything to a variable which is "dead" at the point of the assignment. Some compilers and static analyzers will even warn about dead writes. So, various people's mileage varies on this one. Personally, I agree with Daniel's original code, and disagree with Mark. But I've worked in places that agree with Mark. – Quuxplusone Sep 12 '12 at 22:03

Although it won't fail often, especially not in toy programs, it is still a good idea to check that malloc() (and realloc() and calloc() when you use them) haven't returned a null pointer. And, when you use realloc(), you do not assign the result to the variable passed as the first argument. That is, do not use:

ptr = realloc(ptr, newsize);


Use:

newptr = realloc(oldptr, newsize);


An alternative that is often sufficient is to use a cover function (emalloc() and xmalloc() are both used for the purpose) that guarantees not to return a null pointer.

void *emalloc(size_t nbytes)
{
void *ptr = malloc(nbytes);
if (ptr == 0)
abort();
return(ptr);
}


You can use more elegant mechanisms than abort() to report the error. Use symmetric cover functions for realloc(), calloc() and free().

I recommend three improvements, one major and two minor.

The minor one first: Don't pad out with spaces to horizontally align tokens. There's nothing wrong with doing it, it'll just end up taking time to keep everything aligned, or you'll end up not bothering (because your in a hurry perhaps) and have inconsistent alignment.

Secondly, typedef your structure:

typedef struct BTnode_def
{
int data;
struct BTnode_def *left, *right;
} BTnode;


so you can just use BTnode instead of struct BTnode.

The major one: Don't use prototypes when you can use the function/structure itself as the prototype. You can get rid of the whole prototype section in your code. You'll need to move bt_node_create up a bit though. This will decrease maintenance time - when you change a function's parameters / return value, you only need to do it once.

Oh, and I've just noticed that there appears to be a few C++ features in your code, so it's not pure C code.

UPDATE

I've removed the prefixed underscore (I actually don't do that normally). I'm not sure about the comment mentioning the namespace thing as C doesn't have namespaces.

As for C++ features (I'm not up to date with the C specification so some of these may be in the latest spec):

• Single line comments are C++
• Declarations at any point in the code are C++, C requires declarations to be at the start of the block, i.e. after a {.

ANOTHER UPDATE

This is a personal preference, but I like to put the point * next to the symbol without a white space:

// Instead of this
BTNode * bt_node_create (...);
// I like
BTNode *bt_node_create (...);


which, for me, makes it quicker to differentiate between multiplication and pointer dereferences:

a * func ();  // an expression: a times return value of func
a *func ();   // a declaration: func returns a pointer to type a


I know that the context of the above would disambiguate between the two, but that requires extra parsing by my brain of the adjacent code, and the less my brain has to do the better (it is an old brain after all and not as good as the ones these young people on here have ;-) ).

• Which features are those? I compiled with cc and gcc, and I was under the impression that those compilers didn't support any C++ features. – Daniel Standage Feb 3 '11 at 1:22
• Don't put the _ before BTNode. This makes the identifier clash with the reserved identifiers. Also struct and typedef identifiers do not share the same namespace so just call it BTnode in both cases. – Martin York Feb 3 '11 at 1:25
• @Daniel Standage: I like the horizontal white space. I always do that I think it makes the code easier to read. Don;t be scared of lots of white space. – Martin York Feb 3 '11 at 1:42
• C99 supports those new features. It also supports the const keyword. My understanding is that after C++ came out, some of the non-OO features were incorporated into the C standard. – Michael K Feb 3 '11 at 19:19
• I find it nice when things line up horizontally, but recognize that it's seldom worth the effort because programming/editing tools have no concept of how to do such formatting. I've often wished for a program editor which would allow format-related markup in a fashion that was transparent to the compiler, but I'm unaware of any. – supercat Feb 3 '11 at 20:54

A couple things in addition to the suggestions made already:

• As @Martin said, bt_node_delete deletes a branch of the tree. I think a good term for that may be "prune".
1. list = (int *) malloc( ((maxnodes * 2)+1) * sizeof(int));
2. list = (int *) malloc( ((maxnodes * 2) + 1) * sizeof(int) );
3. list = (int *) malloc(((maxnodes * 2) + 1) * sizeof(int));
I prefer #3, but #2 is more consistent with spacing in the style you gave.
• Place your pointer operators with the symbol it modifies:
1. struct BTnode * decode(int * list)
2. BTnode *decode(int *list)

Personally I don't like the convention of putting spaces inside parenthesis and square brackets ( statement ). I think it is unnecessary whitespace that is harder to maintain if you need to change the statement.