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

#define BM_TREE_DEPTH 23
#define BM_ITERS      10

typedef struct tree_node {
  long value;
  struct tree_node *left;
  struct tree_node *right;
  struct tree_node *next;  
} tree_node;

/* If CONSISTENT_ORDER, then always allocate
   left tree before right tree: */
#define CONSISTENT_ORDER 1

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

  /* For list_sum: */
  tn->next = NULL;
  if (prev)
    prev->next = tn;
  prev = tn;

  return tn;
}

/* Sums the tree by cheating, since tree nodes have been linked into a
   list by make_tree(): */
long list_sum(tree_node *tn) {
  long sum = 0;
  
  while (tn != NULL) {
    sum += tn->value;
    tn = tn->next;
  }
  return sum;
}

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

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

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

/* Make sure our manual stack is deep enough to handle the
   benchmark: */
#define STACK_DEPTH (BM_TREE_DEPTH * 4)

long stack_tree_sum(tree_node *tn) {
  tree_node *stack[STACK_DEPTH];
  int stack_pos = 0;
  long sum = 0;
 
  stack[stack_pos++] = tn;
  while (stack_pos) {
    tn = stack[--stack_pos];
    if (tn) {
      sum += tn->value;
      stack[stack_pos++] = tn->left;
      stack[stack_pos++] = tn->right;
    }
  }

  return sum;
}

long sort_stack_tree_sum(tree_node *tn) {
  tree_node *stack[STACK_DEPTH];
  int stack_pos = 0;
  long sum = 0;
 
  stack[stack_pos++] = tn;
  while (stack_pos) {
    tn = stack[--stack_pos];
    if (tn) {
      sum += tn->value;
      if ((uintptr_t)tn->left < (uintptr_t)tn->right) {
        stack[stack_pos++] = tn->right;
        stack[stack_pos++] = tn->left;
      } else {
        stack[stack_pos++] = tn->left;
        stack[stack_pos++] = tn->right;
      }
    }
  }

  return sum;
}

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

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