#include <iostream>

using namespace std;

struct tree {

short int key;

tree *left;

tree *right;

};

tree *root = NULL;

int c = 0;

struct tree *ctree(tree *root, tree *r, int key) {

if (!r) {

r = new tree;

r->left = NULL;

r->right = NULL;

r->key = key;

if (!root) return r;

if (key % 2 == 0) root->right = r;

else root->left = r;

return r;

}

if (key % 2 == 0) ctree(r, root->right, key);

else ctree(r, root->left, key);

return root;

}

void preorder(tree *root) {

if (!root) return;

if (root->key) cout << root->key << " ";

preorder(root->left);

preorder(root->right);

c++;

}

void Destroy(tree *root) {

if (root) {

Destroy(root->left);

Destroy(root->right);

delete root;

}

root = 0;

}

int main() {

short int key;

cout << "Eneter '0' if u want to exite." << endl;

do {

cout << "key: ";

cin >> key;

root = ctree(root, root, key);

} while (key != 0);

preorder(root);

cout << endl << "The depth of tree is: " << (c -1) / 2<< endl;

Destroy(root);

system("pause");

return 0;

}