#include <stdio.h>
#include <stdlib.h>
#include "tree.h"

/* The original code, where `CONSISTENT_ORDER` and
   `tree_node` versus `backward_tree_node` are selected
   by modifying the source. */

int CONSISTENT_ORDER = 0;

static tree_node *make_tree(int depth) {
  tree_node *tn;
  static tree_node *prev = NULL;

  tn = malloc(sizeof(tree_node));
  tn->value = depth;
  if (depth > 0) {
    if (CONSISTENT_ORDER) {
      tn->left = make_tree(depth - 1);
      tn->right = make_tree(depth - 1);
    } else {
      if (depth & 0x1) {
        tn->left = make_tree(depth - 1);
        tn->right = make_tree(depth - 1);
      } else {
        tn->right = make_tree(depth - 1);
        tn->left = make_tree(depth - 1);
      }
    }
  } else {
    tn->left = NULL;
    tn->right = NULL;
  }

  return tn;
}

static long tree_sum(tree_node *tn) {
  if (tn == NULL)
    return 0;
  else {
    long sum = tn->value;
    sum += tree_sum(tn->left);
    sum += tree_sum(tn->right);
    return sum;
  }
}

static long backward_tree_sum(tree_node *tn) {
  if (tn == NULL)
    return 0;
  else {
    long sum = tn->value;
    sum += backward_tree_sum(tn->right);
    sum += backward_tree_sum(tn->left);
    return sum;
  }
}

#define BM_TREE_DEPTH 23
#define BM_ITERS      10

int main() {
  tree_node *tn;
  int i;
  long sum = 0;

  tn = make_tree(BM_TREE_DEPTH);

  for (i = 0; i < BM_ITERS; i++) {
    /* Pick one of the sum functions: */
    sum += tree_sum(tn);
  }

  printf("%ld\n", sum);

  return 0;
}