//****************************************************************************
//
//    Binary Tree routines from Chapter 12 of Nyhoff data structures text
//      version 1.0
//
//****************************************************************************

#include <iostream>
#include <iomanip>          // needed for the setw function

using namespace std;

class BST
{
    public:
        BST();
        bool empty() const;
        bool search(const int & value) const;
        void inorder(ostream & out) const;
        void graph(ostream & out) const;
        void insert(const int & value);

    private:
        class BinNode
        {
            public:
            int data;
            BinNode * left;
            BinNode * right;

            BinNode() : left(0), right(0) {}        // default costructor
            BinNode(int value)
            : data(value), left(0), right(0)        // constructor with data
            {}
        };  // end of class binNode declaration
        typedef BinNode * BinNodePointer;
        BinNodePointer myRoot;

            // *** private function members follow *** //
        void search2(const int & value, bool & found,
                     BinNodePointer & locptr, BinNodePointer & parent) const;

        void inorderAux(ostream & out, BST::BinNodePointer subtreePtr) const;

        void graphAux(ostream & out, int indent,
                      BST::BinNodePointer subtreeRoot) const;

};  // end of class declaration

inline BST::BST()                         // constructor definition
: myRoot(0)
{}

inline bool BST::empty() const            // determine if node is empty
{ return myRoot ==0; }

bool BST::search(const int & value) const
{
    BST::BinNodePointer locptr = myRoot;
    bool found = false;
    while (!found && locptr != 0)
    {
        if (value < locptr->data)       // descend left
            locptr = locptr->left;
        else if (locptr->data < value)  // descend right
            locptr = locptr->right;
        else
            found = true;
    }
    return found;
}
inline void BST::inorder(ostream & out) const
{
 inorderAux(out, myRoot);
}

void BST::inorderAux(ostream & out, BST::BinNodePointer subtreeRoot) const
{
    if (subtreeRoot != 0)
    {
        inorderAux(out, subtreeRoot->left);     // L operation
        out << subtreeRoot->data << " ";        // V operation
        inorderAux(out, subtreeRoot->right);    // R operation
    }
}

inline void BST::graph(ostream & out) const
{ graphAux(out, 0, myRoot); }

void BST::graphAux(ostream & out, int indent,
                   BST::BinNodePointer subtreeRoot) const
{
    if (subtreeRoot != 0)
    {
        graphAux(out, indent + 8, subtreeRoot->right);
        out << setw(indent) << " " << subtreeRoot->data << endl;
        graphAux(out, indent + 8, subtreeRoot->left);
    }
}

void BST::insert(const int & value)
{
    BST::BinNodePointer
        locptr = myRoot,        // search pointer
        parent = 0;             // pointer to parent of current node
    bool found = false;         // indicates if item already in BST

    while (!found && locptr != 0)
    {
        parent = locptr;
        if (value < locptr->data)       // descend left
            locptr = locptr->left;
        else if (locptr->data < value)  // descend right
            locptr = locptr->right;
        else                            // item found
            found = true;
    }
    if (!found)
    {
        locptr = new BST::BinNode(value);
        if (parent == 0)                // empty tree
            myRoot = locptr;
        else if (value < parent->data)
            parent->left = locptr;      // insert to left of parent
        else
            parent->right = locptr;     // insert to right of parent
    }
    else
        cout << "Item already in the tree\n";
}

int main()
{

    cout << "Hello world!" << endl;
    return 0;
}