#include <stdexcept>
#include <iostream>
struct Tree
{
	Tree* root;
	Tree* left;
	Tree* right;
	int value;
};

class TrainComposition
{
private:
	Tree* tree;
public:
	TrainComposition()
	{
		tree = new Tree();
		tree->root = nullptr;
		tree->left = nullptr;
		tree->right = nullptr;
		tree->value = 0;
	}
	~TrainComposition()
	{
		delete tree;
	}
	void attachWagonFromLeft(int wagonId)
	{
		auto *temp = new Tree();
		temp->root = &findLastLeft(*tree);
		temp->value = wagonId;
		temp->root->left = temp;
		temp->left = nullptr;
		temp->right = nullptr;
	}
	
	void attachWagonFromRight(int wagonId)
	{
		auto *temp = new Tree();
		temp->root = &findLastRight(*tree);
		temp->value = wagonId;
		temp->root->right = temp;
		temp->left = nullptr;
		temp->right = nullptr;
	}

	int detachWagonFromLeft()
	{
		auto temp = findLastLeft(*tree);
		if (temp.root == nullptr && temp.root->right != nullptr)
			return temp.root->right->value;
		temp.root->left = nullptr;
		return temp.value;
	}

	int detachWagonFromRight()
	{
		auto temp = findLastRight(*tree);
		if (temp.root == nullptr && temp.root->left != nullptr)
			return temp.root->left->value;
		temp.root->right = nullptr;
		return temp.value;
	}

	Tree& findLastLeft(Tree& t)
	{
		if (t.left == nullptr)
			return t;
		findLastLeft(*t.left);
	}
	Tree& findLastRight(Tree& t)
	{
		if (t.right == nullptr)
			return t;
		findLastRight(*t.right);
	}
};

#ifndef RunTests
int main()
{
	TrainComposition tree;
	tree.attachWagonFromLeft(7);
	tree.attachWagonFromLeft(13);
	tree.attachWagonFromRight(8);
	std::cout << tree.detachWagonFromRight() << "\n"; // 7 
	std::cout << tree.detachWagonFromLeft(); // 13
	return EXIT_SUCCESS;
}
#endif