/* Mesurer la hauteur d'un arbre binaire mutable avec l'algorithme

     Joseph M. Morris
     Traversing binary trees simply and cheaply
     Information Processing Letters 9(5), 1979
*/

#include <stdlib.h>
#include <assert.h>

int max(int x, int y) { return x > y ? x : y; }

typedef struct T* tree;
struct T { tree left, right; };

int morris(tree t) {
  int d = 0, h = 0;
  while (t != NULL) {
    if (t->left == NULL) {
      t = t->right;
      h = max(h, ++d);
    } else {
      tree p = t->left;
      int delta = 1;
      while (p->right != NULL && p->right != t) {
        p = p->right;
        delta++;
      }
      if (p->right == NULL) {
        p->right = t;
        t = t->left;
        h = max(h, ++d);
      } else {
        p->right = NULL;
        t = t->right;
        d -= delta;
      }
    }
  }
  return h;
}

// tests

tree Node(tree left, tree right) {
  tree t = (tree)malloc(sizeof(struct T));
  t->left = left;
  t->right = right;
  return t;
}

int height(tree t) {
  if (t == NULL) return 0;
  return 1 + max(height(t->left), height(t->right));
}

tree left(tree t, int n) {
  if (n == 0) return t;
  return left(Node(t, NULL), n-1);
}

tree right(tree t, int n) {
  if (n == 0) return t;
  return right(Node(NULL, t), n-1);
}

tree randomtree(int n) {
  if (n == 0) return NULL;
  int n1 = rand() % n;
  return Node(randomtree(n1), randomtree(n-1-n1));
}

int main() {
  for (int n = 0; n < 100; n++) {
    assert(morris(left(NULL, n)) == n);
    assert(morris(right(NULL, n)) == n);
    tree t = randomtree(n);
    assert(height(t) == morris(t));
  }
}

/* Local Variables: */
/* compile-command: "gcc morris.c -o morris" */
/* End: */