#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

//Full Name: Oded Balter
//ID: 206913097

typedef struct listNode {

	int data;

	struct listNode* next;

} ListNode;

typedef struct list {

	ListNode* head;

	ListNode* tail;

} List;

typedef struct  treeNode {

	int data;

	struct treeNode* parent;

	struct treeNode* left;

	struct treeNode* right;

} TreeNode;

typedef struct tree {

	TreeNode* root;

	List leafList;   /*øùéîä î÷åùøú ùì ëì äòìéí áòõ*/

} Tree;



#define LEFT  0

#define RIGHT 1


#define SIZE 100

Tree BuildTreeFromArrayWithLeafList(int  *arr, int  size);
void BuildTreeFromArrayWithLeafListRec(TreeNode** node, int *arr, int size, TreeNode* p, List* leafList);
TreeNode* findParent(Tree tr, int parentData, int branchSelect);
TreeNode* findParentRec(TreeNode* node, int parentData, int branchSelect);
Tree AddLeaf(Tree tr, TreeNode *p, int branchSelect, int data);
void AddNewDataToListAccordingToPosition(List* lst, int position, int NewData, TreeNode* p, int branchSelect);
void insertNodeToTail(List* lst, ListNode* newTail);
void insertNodeAsHead(List* lst, ListNode* newHead);
ListNode* createNode(int data);
void FindThePositionBeforeNewNode(TreeNode* node, TreeNode* New, int *found, int *position);
TreeNode* createNewTreeNode(char data, TreeNode* left, TreeNode* right, TreeNode *p);
void printTreeInorder(Tree tr);
void printTreeInorderRec(TreeNode* root);
void printLeafList(Tree tr);
void freeTree(Tree tr);
void freeTreeRec(TreeNode *root);
void freeList(List lst);
void checkAllocation(void* ptr);
List makeEmptyList();


void main()
{

	int size, i;

	int arr[SIZE];

	Tree tr;

	TreeNode * p;

	int parentData, data, branchSelect;

	scanf("%d", &size);

	for (i = 0; i<size; i++)
		scanf("%d", &arr[i]);

	scanf("%d%d%d", &parentData, &data, &branchSelect);

	tr = BuildTreeFromArrayWithLeafList(arr, size);//the array is given as described in question 1

	p = findParent(tr, parentData, branchSelect); //scan the tree inorder (LDR) and find the first parent (a node with parentData as data) that has no child in branchSelect

	tr = AddLeaf(tr, p, branchSelect, data);

	printTreeInorder(tr); //Print the tree in-order (LDR)

	printLeafList(tr); //Print the leaves from left to right

	freeTree(tr);

}

Tree BuildTreeFromArrayWithLeafList(int  *arr, int  size)
{
	Tree tr;
	tr.leafList = makeEmptyList();
	tr.root = createNewTreeNode(0, NULL, NULL, NULL);
	BuildTreeFromArrayWithLeafListRec(&(tr.root), arr, size, NULL, &(tr.leafList));

	return tr;
}

void BuildTreeFromArrayWithLeafListRec(TreeNode** node, int *arr, int size, TreeNode* p, List* leafList)
{
	if (arr[size / 2] == -1)
		*node = NULL;

	else if (size == 3)
	{
		TreeNode* left;
		TreeNode* right;

		*node = createNewTreeNode(arr[1], NULL, NULL, p);

		if (arr[0] == -1)
			left = NULL;
		else
		{
			left = createNewTreeNode(arr[0], NULL, NULL, *node);
			insertNodeToTail(leafList,createNode(arr[0]));  //creates a new listnode of the leave
		}

		if (arr[2] == -1)
			right = NULL;
		else
		{
			right = createNewTreeNode(arr[2], NULL, NULL, *node);
			insertNodeToTail(leafList, createNode(arr[2]));  //creates a new listnode of the leave
		}

		(*node)->left = left;
		(*node)->right = right;

		if((*node)->right==NULL && (*node)->left ==NULL)
			insertNodeToTail(leafList, createNode((*node)->data));  //creates a new listnode of the leave
	}


	else
	{
		*node = createNewTreeNode(arr[size / 2], NULL, NULL, p);
		BuildTreeFromArrayWithLeafListRec(&((*node)->left), arr, size / 2, *node, leafList);
		BuildTreeFromArrayWithLeafListRec(&((*node)->right), arr + (size / 2) + 1, size / 2, *node, leafList);

		if ((*node)->right == NULL && (*node)->left == NULL)
			insertNodeToTail(leafList, createNode((*node)->data));  //creates a new listnode of the leave
	}
}

TreeNode* findParent(Tree tr, int parentData, int branchSelect)
{
	return findParentRec(tr.root, parentData, branchSelect);
}

TreeNode* findParentRec(TreeNode* node, int parentData, int branchSelect)
{
	TreeNode *left, *right;

	if (node == NULL)
		return NULL;


	if (node->data == parentData && ((node->left == NULL && branchSelect == LEFT) || (node->right == NULL && branchSelect == RIGHT)))  //checks if is the parent
		return node;

	left = findParentRec(node->left, parentData, branchSelect);
	if (left != NULL && left->data == parentData)
		return left;  //if found as a parent in later recursion stages, returns.

	else
	{
		right = findParentRec(node->right, parentData, branchSelect);
		if (right != NULL && right->data == parentData)
			return right;  //if found as a parent in later recursion stages, returns
	}

}

Tree AddLeaf(Tree tr, TreeNode *p, int branchSelect, int data)
{
	int position = 0, found = 0;
	TreeNode *New = NULL;
	New = createNewTreeNode(data, NULL, NULL, p);

	if (branchSelect == RIGHT)
	{
		p->right = New;
	}

	if (branchSelect == LEFT)
	{
		p->left = New;
	}

	//enters the node accordingly

	FindThePositionBeforeNewNode(tr.root, New, &found, &position);  //an algoritem that counts the number of leaves before the New
	AddNewDataToListAccordingToPosition(&(tr.leafList), position, New->data, p, branchSelect);  //adds a node which represents New to the leafList


	return tr;
}

void AddNewDataToListAccordingToPosition(List* lst, int position, int NewData, TreeNode* p, int branchSelect)
{
	ListNode* curr = lst->head;

	for (int i = 0; i <= position && curr != NULL; i++)
	{
		if (i == position)
		{
			if ((branchSelect == LEFT && p->right == NULL) || (branchSelect == RIGHT && p->left == NULL))  //at that case, curr is pointing in the parent if it was a leave
			{
				if (i == 0)
					curr->data = NewData;   //in that case, the curr which is the parent, is the head, replaces the parent, which is not a leave anymore

				else
				curr->next->data = NewData;  //in that case, curr->next is the parent, since curr "goes forward" for every time i!=0 (see end of the while loop)

				break;
			}

			else  //in another case, which the New node isnt supposed to replace the parent, positions accordingly
			{
				ListNode* New = createNode(NewData);

				if (curr == lst->tail)
				{
					insertNodeToTail(lst, New);
					break;
				}

				if (i == 0)
				{
					insertNodeAsHead(lst, New);
					break;
				}

				else
				{
					New->next = curr->next;
					curr->next = New;
					break;
				}
			}

		}

		if (i != 0)
			curr = curr->next;
	}
}

void insertNodeToTail(List* lst, ListNode* newTail)
{
	newTail->next = NULL;

	if (lst->head == NULL)
		lst->head = lst->tail = newTail;
	else
	{
		lst->tail->next = newTail;
		lst->tail = newTail;
	}
}

void insertNodeAsHead(List* lst, ListNode* newHead)
{
	if (lst->head == NULL)
		lst->head = lst->tail = newHead;

	else
	{
		newHead->next = lst->head;
		lst->head = newHead;
	}

}

ListNode* createNode(int data)
{
	ListNode *result;

	result = (ListNode *)malloc(sizeof(ListNode));
	checkAllocation(result);

	result->data = data;
	result->next = NULL;

	return result;
}

void FindThePositionBeforeNewNode(TreeNode* node, TreeNode* New, int *found, int *position)
{
	if (node != NULL)
	{
		if (node->left == NULL && node->right == NULL && node == New)
			*found = 1;  //marks as found

		if (node->left == NULL && node->right == NULL && node != New)
			(*position)++;  //is a leave which isnt New, then adds one as one leave more before the position of New


		FindThePositionBeforeNewNode(node->left, New, found, position);
		if (*found == 1)
			return;

		FindThePositionBeforeNewNode(node->right, New, found, position);

		if (*found == 1)
			return;
	}

} //an algoritem that counts the number of leaves before the New

TreeNode* createNewTreeNode(char data, TreeNode* left, TreeNode* right, TreeNode *p)
{
	TreeNode* res = (TreeNode*)malloc(sizeof(TreeNode));
	checkAllocation(res);

	res->data = data;
	res->left = left;
	res->right = right;
	res->parent = p;

	return res;
}

void printTreeInorder(Tree tr)
{
	printTreeInorderRec(tr.root);
	printf("\n");
}

void printTreeInorderRec(TreeNode* root)
{
	if (root == NULL)
		return;
	else
	{
		printTreeInorderRec(root->left);
		printf("%d ", root->data);
		printTreeInorderRec(root->right);
	}
}

void printLeafList(Tree tr)
{
	ListNode* curr = (tr.leafList).head;

	while (curr!=NULL)
	{
		printf("%d ", curr->data);
		curr = curr->next;
	}
}

void freeTree(Tree tr)
{
	freeList(tr.leafList);
	freeTreeRec(tr.root);
}

void freeTreeRec(TreeNode *root)
{
	if (root != NULL)
	{
		freeTreeRec(root->left);
		freeTreeRec(root->right);
		free(root);
	}
}

void freeList(List lst)
{
	ListNode* curr = lst.head, *saver;

	while (curr != NULL)
	{
		saver = curr->next;
		free(curr);
		curr = saver;
	}
}

void checkAllocation(void* ptr)
{
	if (ptr == NULL)
	{
		printf("Allocation error\n");
		exit(-1);
	}
}

List makeEmptyList()
{
	List res;

	res.head = res.tail = NULL;

	return res;
}