Traversing a BST in iterative inorder

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 nodestack;
typedef vector 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 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 --------- /

/* ---

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.

-
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.

StackExchange Code Review Q#2422, answer score: 2