I implemented a solution to [this coding challenge][1] 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!


  [1]: http://codegolf.stackexchange.com/questions/339/binary-tree-encoding