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
#include
#include

// 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_enc

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.

StackExchange Code Review Q#569, answer score: 16