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


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