#include <iostream>
using namespace std;

const int nil = 0;
class treenode_type
{
public:
    int info;
    treenode_type *left;
    treenode_type *right;
};

void setleft(int x);
void setright(int x);
void inorder(treenode_type *p);
void preorder(treenode_type *p);
void postorder(treenode_type *p);
treenode_type *p, *q, *root;
int number;

void main()
{
    cout << "Enter first value: \n";
    cin >> number;
    cout << number << "\n";
    root = new treenode_type;
    (*root).info = number;
    (*root).left = nil;
    (*root).right = nil;
    cout << "Enter other numbers terminated by -999\n";
    cin >> number;
    while (number != -999)
    {
        p = root;
        q = p;
        while ((number != (*p).info) && (q!=nil))
        {
            p = q;
            if (number < (*p).info)
                q = (*p).left;
            else
                q = (*p).right;
        }
        if (number == (*p).info)
            cout << number << " is a duplicate \n";
        else if (number < (*p).info)
        {
            setleft(number);
            cout << number << " is a left child of " << (*p).info << "\n";
        }
        else
        {
            setright(number);
            cout << number << " is a right child of " << (*p).info << "\n";
        }
        cin >> number;
    }
    cout << "The tree traversed INORDER is \n";
    p = root;
    inorder(p);

    cout << "The tree traversed PREORDER is \n";
    p = root;
    preorder(p);

    cout << "The tree traversed POSTORDER is \n";
    p = root;
    postorder(p);
}
void setleft(int x)
{
    treenode_type *q;
    q = new treenode_type;
    (*q).info = x;
    (*q).left = nil;
    (*q).right = nil;
    (*p).left = q;
}
void setright(int x)
{
    treenode_type *q;
    q = new treenode_type;
    (*q).info = x;
    (*q).left = nil;
    (*q).right = nil;
    (*p).right = q;
}
void inorder(treenode_type *r)
{
    if (r != nil)
    {
        inorder((*r).left);
        cout << (*r).info << "\n";
        inorder((*r).right);
    }
}
void preorder(treenode_type *r)
{
    if (r != nil)
    {
        cout << (*r).info << "\n";
        preorder((*r).left);
        preorder((*r).right);
    }
}
void postorder(treenode_type *r)
{
    if (r != nil)
    {
        postorder((*r).left);
        postorder((*r).right);
        cout << (*r).info << "\n";
    }
}

void inorder(treenode_type *r, int depth)
{
    if (r != nil)
    {
        inorder((*r).left,depth+1);
        cout << (*r).info << " : " << depth << "\n";
        inorder((*r).right,depth+1);
    }
}