O(n)-time non-recursive traversal of binary trees without extract space cost.

binary-tree-traversal.cc

#include <iostream>

struct Node {
  int key;
  Node* left;
  Node* right;
  Node* parent;

  Node(int k, Node* l, Node* r) {
    key = k;
    left = l;
    right = r;
    parent = NULL;
  }
};

Node* first_kid(Node* root) {
  if (root->left != NULL)
    return root->left;
  if (root->right != NULL)
    return root->right;
  return NULL;
}

Node* last_kid(Node* root) {
  if (root->right != NULL)
    return root->right;
  if (root->left != NULL)
    return root->left;
  return NULL;
}

void traverse(Node* root) {
  if (root == NULL) {
    return;                     // empty tree
  }

  Node* prev = NULL;
  Node* current = root;
  Node* next = NULL;

  while (current != NULL) {
    if (prev == current->parent) {
      std::cout << current->key << "\n";

      if (current->left != NULL)
        current->left->parent = current;
      if (current->right != NULL)
        current->right->parent = current;

      prev = current;
      next = first_kid(current);
      if (next != NULL)
        current = next;
      else
        current = current->parent;
    }
    else if (prev == first_kid(current)) {
      prev = current;
      next = last_kid(current);
      if (next != first_kid(current))
        current = next;
      else
        current = current->parent;
    }
    else if (prev == last_kid(current)) {
      prev = current;
      current = current->parent;
    }
  }
}

int main() {
  Node* r = new Node(1,
                     NULL, // new Node(2, NULL, NULL),
                     new Node(3, NULL, NULL));
  traverse(r);
  return 0;
}