#ifndef _KTREE_H_
        #define _KTREE_H_

        #include "dsexceptions.h"
        #include <iostream.h>       // For NULL

        template <class Object>
        class KTree;

        template <class Object>
        class TreeItr;     // Incomplete declaration.

        template <class Object>
        class KTreeNode
        {
	private:
            Object element;
	    int size;
            KTreeNode *nextSibling;
            KTreeNode *firstChild;

            KTreeNode( const Object & theElement, int sz, KTreeNode *ns, KTreeNode *fc )
              : element( theElement ), size (sz), nextSibling( ns ), firstChild( fc ) { }
            friend class KTree<Object>;
            friend class TreeItr<Object>;
        };


        // KTree class
        //
        // CONSTRUCTION: with ITEM_NOT_FOUND object used to signal failed finds
        //
        // ******************PUBLIC OPERATIONS*********************
        // void insert( x, sz, itr )       --> Insert x
        // void remove( x )       --> Remove x
        // TreeItr<Object> find( x )   --> Return location of item that matches x
        // TreeItr<Object> findParent( x )   --> Return location of parent item of x
        // boolean isEmpty( )     --> Return true if empty; else false
        // void makeEmpty( )      --> Remove all items
        // void printTree( )      --> Print tree in sorted order

        template <class Object>
        class KTree
        {
          public:
            explicit KTree();
            KTree( const KTree & rhs );
            ~KTree( );

            TreeItr<Object> zeroth( ) const;
            TreeItr<Object> find( const Object & x ) const;
            TreeItr<Object> find( const Object & x, 
				const TreeItr<Object> &itr ) const;
            TreeItr<Object> findParent( const Object & x ) const;
            bool isEmpty( ) const;
            void printTree( ) const;

            void makeEmpty( );
            void insert( const Object & x, int sz, const TreeItr<Object> &itr );
            void remove( const Object & x );

            const KTree & operator=( const KTree & rhs );
	    void percolate();
	    void rinse();

          private:
            KTreeNode<Object> *root;
	    TreeItr<Object> rootitr;
            const Object ITEM_NOT_FOUND;

            const Object & elementAt( KTreeNode<Object> *t ) const;

            void insert( const Object & x, int sz, KTreeNode<Object> * & t ) ;
            int remove( const Object & x, KTreeNode<Object> * & t ) const;
            KTreeNode<Object> * find( const Object & x, KTreeNode<Object> *t ) const;
            KTreeNode<Object> * findParent( const Object & x, KTreeNode<Object> *t ) const;
            void makeEmpty( KTreeNode<Object> * & t ) const;
            void printTree(KTreeNode<Object> *t, char * ) const;
            KTreeNode<Object> * clone( KTreeNode<Object> *t ) const;
	    int percolate(KTreeNode<Object> *);
	    void rinse(KTreeNode<Object> *);
        };


        // TreeItr class; maintains "current position"
        //
        // CONSTRUCTION: Package friendly only, with a KTreeNode
        //
        // ******************PUBLIC OPERATIONS*********************
        // bool isPastEnd( )      --> True if past end position in tree
        // Object retrieve        --> Return item in current position

        template <class Object>
        class TreeItr
        {
          public:
            TreeItr( ) : current( NULL ) { }
            bool isPastEnd( ) const
              { return current == NULL; }
	    void over() {if (isPastEnd()) throw BadIterator();
		current = current->nextSibling; }
	    void down() {if (isPastEnd()) throw BadIterator();
		current = current->firstChild;}
            const Object & retrieve( ) const
              { if( isPastEnd( ) ) throw BadIterator( );
                return current->element; }
            int retrieveSize( ) const
              { if( isPastEnd( ) ) throw BadIterator( );
                return current->size; }

          private:
            KTreeNode<Object> *current;    // Current position

            explicit TreeItr( KTreeNode<Object> *theNode )
              : current( theNode ) { }

            friend class KTree<Object>; // Grant access to constructor
        };

        #endif