#include <stdio.h>
 
struct Node {
	Node(Node *left, Node *right, int val) : left(left), right(right), next(NULL), val(val) {}
	Node *left, *right, *next;
	int val;
};
 
void LinkTreeWithoutNils (Node* node)
{
  if (!node) 
    return;
  Node *left = node->left, *right = node->right;
  LinkTreeWithoutNils(left);
  LinkTreeWithoutNils(right);
  while (left)
  {
    left->next = right;
    left = left->right ? left->right : left->left;
    if (right) right = right->left;
  }    
}
 
void LinkTree (Node* node)
{
  LinkTreeWithoutNils(node);  
  Node* right = node;
  while (right)
  {
    right->next = NULL;
    right = right->right;
  }
}
 
void ShowNode(Node *node)
{
	printf("val=%d left=%d right=%d next=%d\n", node->val,
	    node->left ? node->left->val : -1,
	    node->right ? node->right->val : -1,
	    node->next ? node->next->val : -1);
}
 
int main(void) {
	Node leaf1(NULL, NULL, 1);
	Node leaf2(NULL, NULL, 3);
	Node mid1(&leaf1, NULL, 4);
	Node mid2(NULL, &leaf2, 5);
	Node root(&mid1, &mid2, 6);
	LinkTree(&root);
 
	ShowNode(&leaf1);
	ShowNode(&leaf2);
	ShowNode(&mid1);
	ShowNode(&mid2);
	ShowNode(&root);
	return 0;
}