Traversing a BST in iterative inorder

Question

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));
}

Answer 1

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.

• Ganesh: Thanks , I had not had time to think of all these small issues. Your first point is especially relevant.