#include <iostream>

using namespace std;

struct element {
       int label;
       element *left,*right;
};

typedef element *node;
typedef element bt;

node ParentB(node n, bt* T) {
    if (n == T) return NULL;
	node parent = NULL;
	if (T->left) {
		if (T->left == n) return T;
		else parent =  ParentB(n, T->left);
	}
	if(T->right) {
		if (T->right == n) return T;
		else parent = ParentB(n, T->right);
	}
	return parent;
}

node LeftChildB(node n, bt* T) {
    if (!n) {
       cout << "Cvor ne postoji!" << endl;
       return NULL;
    }
    if (!n->left) {
       cout << "Cvor nema dijete!" << endl;
       return NULL;
    }
    return n->left;
}

node RightChildB(node n, bt* T) {
    if (!n) {
       cout << "Cvor ne postoji!" << endl;
       return NULL;
    }
    if (!n->right) {
       cout << "Cvor nema dijete!" << endl;
       return NULL;
    }
    return n->right;
}

int LabelB(node n, bt* T) {
    return n->label;
}

void ChangeLabelB(int x, node n, bt* T) {
    if(!n) {
       cout << "Taj element stabla ne postoji!" << endl;
       return;
    }
    n->label = x;
}

node RootB(bt* T) {
    if(!T) return NULL;
    return T;
}

void CreateLeftB(int x, node n, bt* T) {
    if(n->left) {
        cout << "Greska!" << endl << endl;
        return;
    }
    node novi = new element;
    n->left = novi;
    novi->label = x;
    novi->left = NULL;
    novi->right = NULL;
}

void CreateRightB(int x, node n, bt* T) {
    if(n->right) {
        cout << "Greska!" << endl << endl;
        return;
    }
    node novi = new element;
    n->right = novi;
    novi->label = x;
    novi->left = NULL;
    novi->right = NULL;
}

void DeleteB1(node n, bt* T) {
    if(n->left) DeleteB1(n->left, T);
    if(n->right) DeleteB1(n->right, T);
    delete n;
}

void DeleteB(node n, bt* T) {
    node roditelj = ParentB(n, T);

    if(n->left) DeleteB1(n->left, T);
    if(n->right) DeleteB1(n->right, T);

    if(roditelj->left == n) roditelj->left = NULL;
    else roditelj->right = NULL;

    delete n;
}

bt* InitB(int x, bt* T) {
    T = new element;
    T->label = x;
    T->left = NULL;
    T->right = NULL;
    return T;
}