4
\$\begingroup\$

Traverse a binary search tree in iterative inorder.

Note that the iterative methods below contain the meat of the code; the remaining code is included for completeness.

// tree node
struct node 
{
    int elem;

    node *left, *right;

    // Statically create a node, given an element

    static node* create(int elem)
    {
        node *newnode = new node;
        newnode->elem = elem;
        newnode->left = newnode->right = NULL;
        return newnode;
    }   

    // Statically destroy a node

    static void destroy (node *& mynode)
    {
        delete mynode;
        mynode->left = mynode->right = NULL;
    }
};

typedef stack<const node*> nodestack;
typedef vector<const node*> nodevect;


// tree class

class tree
{
    private:
    node *root;
    nodestack mystack;

    public:
    // initialize tree
    tree(int elem) 
    {
        root = node::create(elem);
    }

    /* --------- INSERTION METHODS BEGIN --------- */
    // Insert a new element into a subtree whose root node is given
    bool insert(node *travnode, int elem)
    {
        node *newnode = node::create(elem);
        // Insert to left subtree
        if(elem < travnode->elem)
        {
            if(travnode->left == NULL) 
            {
                travnode->left = newnode;
                return true;
            }
            else  return insert(travnode->left,elem);   
        }
        else
        if(elem == travnode->elem)
        {
            delete newnode;
            return false;
        }
        // Insert to right subtree
        else // if(elem > travnode->elem)
        {
            if(travnode->right == NULL) 
            {
                travnode->right = newnode;
                return true;
            }
            else return insert(travnode->right,elem);   
        }
    }

    // Insert directly into the tree; this method is used externally  
    bool insert(int elem)
    {
        return insert(root,elem);   
    }       

    /* --------- INSERTION METHODS END --------- */

    /* ------- RECURSIVE METHODS BEGIN -----------*/
    // Recursive methods below are used for checking the iterative version
    // Recursive inorder traversal of a node ; dump nodes traversed into a  vector
    void recursive_inorder(const node *mynode, vector<int> &myvect) const 
    {
        if(mynode != NULL)
        {
            recursive_inorder(mynode->left,myvect);
            myvect.push_back(mynode->elem);
            recursive_inorder(mynode->right,myvect);
        }
    }


    // Recursive traversal of the whole tree
    vector<int> recursive_inorder() const
    {
        vector<int> myvect; 
        recursive_inorder(root,myvect);
        return myvect;
    }
    /* -------- RECURSIVE METHODS END -------*/



    /* -------- ITERATIVE METHODS BEGIN ---*/
    //  Go to the leftmost node, stacking nodes along the path 
    void findLeftMostAndStack(const node *mynode) 
    {
        const node *travnode = mynode;
        while(travnode != NULL)
        {
            mystack.push(travnode);
            travnode = travnode->left;  
        }   
    } 

    // Return the stack created thus far
    nodestack getStack() const {return mystack;}

    // Get the first element in inorder traversal, stacking all nodes on the way from the root
    const node* findFirstElement() 
    {
        while(!mystack.empty()) 
            mystack.pop();

        findLeftMostAndStack(root);
        const node *firstNode = mystack.top();
        mystack.pop();

        return firstNode;
    }



    // Given any node, use the stack to find the successor
    const node* findSuccessorOf(const node *mynode)
    {
        // We're at the last node in traversal; there is no successor
        if(mystack.empty() && mynode->right == NULL)
            return NULL;

        // If there is a right child, stack the nodes along the first node in the right subtree  
        if(mynode->right != NULL) 
            findLeftMostAndStack(mynode->right);

        // To find the successor,  
        const node *successor = mystack.top();          
        mystack.pop();
        return successor;
    }


    // Use all the methods above to traverse the tree iteratively inorder
    vector<int> iterative_inorder()
    {
        vector<int> myvect;
        // Get first element
        const node* nextnode = findFirstElement();
        while(nextnode != NULL) // go on till last element is reached
        {
            myvect.push_back(nextnode->elem); 
            // keep finding successors
            nextnode = findSuccessorOf(nextnode);   
        }

        return myvect;
    }

    /* --------------- ITERATIVE METHODS END *--------------*/

    // Friend functions
    friend tree* makeTree(const vector<int> &); // create tree using a vector
    // compare recursive & iterative traversals 
    friend bool compareRecIter(tree &T);


    // Destroy subtree
    void destroy (node *& mynode) 
    { 
        if(mynode == NULL) return;
        destroy(mynode->left); 
        destroy(mynode->right); 
        delete(mynode);
        mynode->left = mynode->right = NULL;
        mynode =  NULL;     
    }

    // Destroy tree
    void destroy() { this->destroy(root);
}; // tree class

/* Auxiliary functions */
// Create a tree from  a vector of elements
tree* makeTree(const vector<int> &v)    
{
    assert(v.size());
    tree *T = new tree(v[0]);
    for(size_t i = 1; i != v.size(); ++i)
        T->insert(v[i]);
    return T;
}  


// Compare recursive & iterative traversals of the tree
// If equal, return true; else false
bool compareRecIter(tree &T)
{
    // Get the 2 vectors, returned by recursive & iterative traversals
    vector<int> v = T.recursive_inorder();
    vector<int> v2 = T.iterative_inorder();
    for(int i=0;i!=v.size();++i) cout<<v[i] <<",";
    cout<<endl;

    for(int i=0;i!=v2.size();++i) cout<<v2[i] <<",";
    cout<<endl;
    // Return true if they are identical
    return (v == v2);   
}

Test code:

int main()
{
    int leftLeaning[5] = {5,4,3,2,1};
    tree *T = makeTree(vector<int>(leftLeaning, leftLeaning + 5));

    assert(compareRecIter(*T)); 
    T->destroy();
    delete T;
    T = NULL;

    cout<<"\n";
    int rightLeaning[5] = {1,2,3,4,5};

    tree* T2 = makeTree(vector<int>(rightLeaning, rightLeaning + 5));
    assert(compareRecIter(*T2));
}
\$\endgroup\$
2
\$\begingroup\$

Your program looks okay for the most part and will probably work without any observable bugs. However there are a couple of problematic areas and sticky points you should address. I'll start with the most important first:

  • Accessing data member of a struct after deletion:

    
    static void node::destroy( node *& mynode )
    {
        delete mynode;
        mynode->left = mynode->right = NULL;
        mynode = NULL;
    }
    
    void tree::destroy( node *& mynode )
    {
        if( mynode == NULL ) return;
        destroy( mynode->left );
        destroy( mynode->right );
        delete( mynode );
        mynode->left = mynode->right = NULL;
        mynode = NULL;
    }    
    

The above two methods contain undefine behavior because you're trying to assign to left and right after mynode got deleted.

  • Leaky encapsulation; methods that should be private are not. For example, the first overloaded insert() method should be private, as your comments suggest here:

  // Insert a new element into a subtree whose root node is given
    bool insert( node *&travnode, int elem )
    //...

  // Insert directly into the tree; this method is used externally
    bool insert( int elem )
    //...
  

As well as a couple other methods that outside code using this tree has no business of knowing. Helper functions and methods like destroy(), overloaded recursive_inorder() and find*() used by your tree iteration comes to mind. They belong in the private tree section. Ideally, code using your tree class should not be exposed to the fact that nodes are being used.

  • RAII should be employed for dynamic node allocation. Your tree class should be responsible for cleaning up its own nodes in the destructor rather than forcing client code to call destroy(). To guard against premature leaks have functions that return dynamically allocated memory, like makeTree(), use a smart pointer like auto_ptr<tree>.

  • Use of tree::destroy() is not orthagonal with node::create(). In fact, node::destroy() doesn't seem to be used at all. It also looks like node::destroy() expects whoever's using it to handle the bottom branches of this node. Not that this is necessarily wrong but something like this needs to be commented so it's clear what assumptions are being made. For example, if the tree class didn't handle the left and right child nodes of the parent node that's being deleted then that entire bottom branch just got disconnected.

  • Awkward initialization in the tree constructor. If you change the constructor to accept a range represented by two iterators rather than a single int, it will make the class that much easier to work with. It'll also get rid of the need for a separate makeTree() function.

  • bool tree::insert( node *&travnode, int elem ) can be refactored with less code. You can do this by pushing the NULL check down to the base case and changing node *travnode into a reference pointer. This also corrects a potential memory leak lurking in your original version.

    
    bool insert( node *&travnode, int elem )
    {
      if( travnode == NULL )
      {
        travnode = node::create( elem );
        return true;
      }
    
      if(travnode->elem == elem ) return false;
    
      node *&correct_branch = elem elem ? travnode->left : travnode->right;
      return insert( correct_branch, elem );
    }
    

Hopefully the above points provided enough detail to help you better refactor your code.

\$\endgroup\$
1
  • \$\begingroup\$ Thanks , I had not had time to think of all these small issues. Your first point is especially relevant. \$\endgroup\$
    – Ganesh
    May 16 '11 at 17:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.