treewalk.c

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

double seconds() {
  struct timespec ts;
  clock_gettime(CLOCK_MONOTONIC, &ts);
  return ts.tv_sec + ts.tv_nsec/1000000000.0;
}

struct node {
  int data;
  struct node* parent;
  struct node* left;
  struct node* right;
};

struct node* mk_tree(struct node *parent, int d) {
  if (d == 0) {
    return NULL;
  } else {
    struct node *x = malloc(sizeof(struct node));
    x->data = 0;
    x->parent = parent;
    x->left = mk_tree(x, d-1);
    x->right = mk_tree(x, d-1);
    return x;
  }
}

void print_tree(int d, struct node* x) {
  if (x) {
    print_tree(d+1, x->left);
    for (int i = 0; i < d; i++) {
      printf(" ");
    }
    printf("%d\n", x->data);
    print_tree(d+1, x->right);
  }
}

void visit(struct node *x) {
  x->data++;
}

void walk_tree_withstack(struct node *x) {
  if (x) {
    visit(x);
    walk_tree_withstack(x->left);
    walk_tree_withstack(x->right);
  }
}

void walk_tree_stackfree(struct node *x) {
  struct node *cur = x;
  struct node *prev = NULL;
  while (cur) {
    struct node *next = cur->parent;
    if (prev == cur->parent) {
      visit(cur);
      if (cur->left) {
        next = cur->left;
      } else if (cur->right) {
        next = cur->right;
      }
    } else if (prev == cur->left) {
      if (cur->right) {
        next = cur->right;
      }
    }
    prev = cur;
    cur = next;
  }
}

void free_tree(struct node* x) {
  if (x) {
    free_tree(x->left);
    free_tree(x->right);
    free(x);
  }
}

int main(int argc, char** argv) {
  if (argc != 2) {
    fprintf(stderr, "Usage: %s N\n", argv[0]);
    exit(1);
  }

  int d = atoi(argv[1]);
  double a,b;

  a = seconds();
  struct node *t = mk_tree(NULL, d);
  b = seconds();
  printf("Constructing:\t\t%fs\n", b-a);

  a = seconds();
  walk_tree_withstack(t);
  b = seconds();
  printf("Walking with stack:\t%fs\n", b-a);

  a = seconds();
  walk_tree_stackfree(t);
  b = seconds();
  printf("Walking without stack:\t%fs\n", b-a);

  a = seconds();
  free_tree(t);
  b = seconds();
  printf("Freeing:\t\t%fs\n", b-a);
}