convert a binary tree to a double linked list in in-order order

tree_to_dlist.cpp

#include <iostream>
using namespace std;

struct Node {
  int value = 0;
  Node* left = nullptr;
  Node* right = nullptr;


};

void Free(Node* node) {
  // if(node->left) { Free(node->left); }
  if(node->right) { Free(node->right); }

  delete node;
}

Node* ToDoubleListImpl(Node* current_node, Node* last_processed_node, Node** head) {
  if(current_node->left) {
    last_processed_node = ToDoubleListImpl(current_node->left, last_processed_node, head);
  }

  // do something
  if(!*head) {
    *head = current_node;
  }
  current_node->left = last_processed_node;
  if(last_processed_node) {
    last_processed_node->right = current_node;
  }
  last_processed_node = current_node;

  if(current_node->right) {
    last_processed_node = ToDoubleListImpl(current_node->right, last_processed_node, head);
  }

  return last_processed_node;
}

Node* ToDoubleList(Node* root) {
  Node* head = nullptr;
  ToDoubleListImpl(root, nullptr, &head);
  return head;
}

void Print(Node* head) {

  Node* forward = head;
  while(forward) {
    cout << forward->value << " -> ";
    forward = forward->right;
  }
  cout << endl;
  Node*  backward = head;
  while(backward) {
    if(backward->left) {
      cout << backward->left->value << " <- ";
    }
    if(!backward->right) {
      cout << backward->value;
    }
    backward = backward->right;
  }
}

// To execute C++, please define "int main()"
int main() {
  Node* root = new Node{
    10,
    new Node {
      12,
      new Node {25},
      new Node {30}
    },
    new Node {
      15,
      new Node {36}
    }
  };

  Node* head = ToDoubleList(root);
  Print(head);

  Free(head);
}