Binary tree encoding

Question

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

  // 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, 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.

Answer 1

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.

Answer 2

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.

Answer 3

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().

Answer 4

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 ;-) ).

Answer 5

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.