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

/// binary tree node type
typedef struct Node {
  struct Node *parent, *left, *right;
  int label;
} Node;

/// initialize an array as a complete binary tree.
int build_tree(Node *parent, Node **self, Node *node, int num, int label) {

  if(!num) {
    *self = NULL;
    return label;
  } else if(self) {
    *self = node;
  }

  const int half = (num - 1) / 2;
  label = build_tree(node, &(node->left), node + 1, half, label);
  label = build_tree(node, &(node->right), node + 1 + half, half, label);

  node->parent = parent;
  node->label = label;

  return label + 1;
}

/// print out a node's label
void print_node_label(Node *node) {
  printf("%d\n", node->label);
}

/// do a postorder traversal of a binary tree
void traverse_recursive(Node *node, void (*visit)(Node *)) {
  if(!node) return;
  traverse_recursive(node->left, visit);
  traverse_recursive(node->right, visit);
  visit(node);
}

/// get a pointer to a child node
Node **find_node_pointer(Node *parent, Node *child) {
  if(child == parent->left) {
    return &(parent->left);
  } else {
    return &(parent->right);
  }
}

/// do a tail-recursive postorder traversal of a binary tree
void traverse_iterative(Node *node, void (*visit)(Node *)) {
  Node *parent = NULL, 
       *prev = NULL;

  // base case: the tree never had nodes
  if(!node) {
    return;
  }

  for(;;) {

    // base case: *source is a leaf node. pretend that we're coming from 
    // the right child  
    if(!node) {
      node = parent;
      parent = NULL;

    // we just finished visiting the right child, visit the current node
    } else if(prev == node->right) {

      visit(node);

      // termination case: we have returned to the root node
      if(!node->parent) {
        return;

      // ascend the tree, we've visited our parent's right child
      } else {
        prev = node;
        node = node->parent;
      }

    // we just finished visiting the left child, visit the right right
    } else if(prev == node->left) {
      parent = node;
      node = node->right;
      prev = NULL;

    // we need to go visit the left child
    } else {
      parent = node;
      node = node->left;
      prev = NULL;
    }
  }
}

int main(void) {
  Node nodes[15];

  build_tree(NULL, NULL, &(nodes[0]), 15, 1);
  traverse_recursive(&(nodes[0]), &print_node_label);
  printf("\n\n");
  traverse_iterative(&(nodes[0]), &print_node_label);
  return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15