Convert a binary tree to a doubly-linked list.

tree_to_list.cpp

template<typename Node>
class TreeToList
{
public:
	
	Node* operator()(Node* root)
	{
		_transform(root, root);
		
		while (root->left) root = root->left;
		
		return root;
	}
	
private:
	
	using pair_t = std::pair<Node*, Node*>;
	
	pair_t _transform(Node* node, Node* root, bool on_left = true)
	{
		if (! node) return {nullptr, nullptr};
		
		auto left = _transform(node->left, root, true);
		
		node->left = left.first;
		
		if (node->left) node->left->right = node;
		
		auto right = _transform(node->right, root, false);
		
		node->right = right.first;
		
		if (node->right) node->right->left = node;
		
		if (node == root) return {root, root};
		
		if (! right.second) right.second = node;
		
		if (on_left && node->right)
		{
			return {right.second, right.second};
		}
		
		else if (! on_left && node->left)
		{
			return _rotate_right(node, right);
		}
		
		return {node, node};
	}
	
	pair_t _rotate_right(Node* node, const pair_t& pair)
	{
		node->left->right = node;
		
		return {node->left, pair.second};
	}
};

template<typename Node>
Node* tree_to_list(Node* root)
{
	TreeToList<Node> transform;
	
	return transform(root);
}