traverse binary tree without extra non-constant space such as dfs and stack.

main.c

#include <stdio.h>

typedef struct Node Node;

struct Node {
  int value;
  Node *left;
  Node *right;
};

void traverse(Node *root) {
  Node *cur = root;

  while (cur != NULL) {
    if (cur->left != NULL) {
      Node *predecessor = cur->left;
      while (predecessor->right != NULL && predecessor->right != cur) {
        predecessor = predecessor->right;
      }

      if (predecessor->right == NULL) {
        printf("pre-order: %d\n", cur->value);
        predecessor->right = cur;
        cur = cur->left;
      } else {
        printf("in-order: %d\n", cur->value);
        predecessor->right = NULL;
        cur = cur->right;
      }
    } else {
      printf("pre-order, in-order: %d\n", cur->value);
      cur = cur->right;
    }
  }
}

int main(void) {
  traverse(&(Node) {
    4,
    &(Node) {
      2,
      &(Node) { 1 },
      &(Node) { 3 },
    },
    &(Node) {
      6,
      &(Node) { 5 },
      &(Node) { 7 },
    },
  });

  return 0;
}

// $ gcc main.c
// $ ./a.out
//
// pre-order: 4
// pre-order: 2
// pre-order, in-order: 1
// in-order: 2
// pre-order, in-order: 3
// in-order: 4
// pre-order: 6
// pre-order, in-order: 5
// in-order: 6
// pre-order, in-order: 7