#include <iostream>
#include<conio.h>

using namespace std;
struct btnode {
	int value;
	struct btnode *l;
	struct btnode *r;
};

typedef struct btnode bt;
bt *root;
bt *New, *list;
bt *create_node();
void display(bt *);
void construct_tree();
void dfs(bt *);

int main()
{
	construct_tree();
	display(root);
	cout << endl;
	cout << "Depth first traversal\n ";
	dfs(root);

	_getch();
	return 0;
}

/* Creates an empty node */
bt * create_node()
{
	New = new bt;
	New->l = NULL;
	New->r = NULL;
	return New;
}

/* Constructs a tree */
void construct_tree()
{
	root = create_node();
	root->value = 50;
	root->l = create_node();
	root->l->value = 20;
	root->r = create_node();
	root->r->value = 30;
	root->l->l = create_node();
	root->l->l->value = 70;
	root->l->r = create_node();
	root->l->r->value = 80;
	root->l->r->r = create_node();
	root->l->r->r->value = 60;
	root->l->l->l = create_node();
	root->l->l->l->value = 10;
	root->l->l->r = create_node();
	root->l->l->r->value = 40;
}

/* Display the elements in a tree using inorder */
void display(bt * list)
{
	if (list == NULL)
	{
		return;
	}
	display(list->l);
	cout << list->value;
	display(list->r);
}

/* Dfs traversal using post order */
void dfs(bt * list)
{
	if (list == NULL)
	{
		return;
	}
	dfs(list->l);
	dfs(list->r);
	cout << list->value;
}