#include<bits/stdc++.h>
	using namespace std;

	typedef struct btNode
	{
	  btNode *left;
	  btNode *right;
	  int data;
	}btNode;


	btNode *create_btNode(int data)
	{
	  btNode *temp = new btNode[1];
	  temp->data = data;
	  temp->left = temp->right = NULL;
	}

	void recFunc(btNode *temp,int type)
	{
	   if((temp->left == NULL)&&(temp->right == NULL))cout << temp->data << " ";
	   else if(type == 1)cout << temp->data << " ";
	   else {;}


	   if(type == 3)
	   {
		if(temp->left)recFunc(temp->left,0);
		if(temp->right)recFunc(temp->right,3);
		cout << temp->data << " ";
	   }   
	   else if(type == 1)
	   {
		if(temp->left)recFunc(temp->left,1);
		if(temp->right)recFunc(temp->right,0);
	   }
	   else if(type == 0)
	   {
		if(temp->left)recFunc(temp->left,0);
		if(temp->right)recFunc(temp->right,0);
	   }
	   else {;}
	}

	void func(btNode *root)
	{
	   if(root != NULL)
	   {
	      cout << root->data << " ";
	      if(root->left)recFunc(root->left,1);
	      if(root->right)recFunc(root->right,3);
	      cout << endl;
	   }
	}


	int main()
	{
		btNode *root = create_btNode(20);
		root->left = create_btNode(8);
		root->left->left = create_btNode(4);
		root->left->right = create_btNode(12);
		root->left->right->left = create_btNode(10);
		root->left->right->right = create_btNode(14);
		root->right = create_btNode(22);
		root->right->right = create_btNode(25);
		func(root);
	  return 0;
	}