Non Recursive Binary Tree Traversal using Stack

//Inorder tree traversal non recursive.

template<typename T> void BST<T>::inorder_non_recursive(NODE<BT>* nptr)

{

    cout << endl;

    stack<NODE<BT>*> s;

    while (!s.empty() || nptr)

    {

        /*If nptr is NULL, we need to pop from top of the stack

        and print it's value. Then traverse the right sub-tree*/

        if (!nptr)

        {

            nptr = s.top();

            cout << nptr->data << "\t";

            nptr = nptr->right;

            s.pop();

        }

        /*Keep traversing left unless nptr is NULL*/

        if (nptr)

        {

            s.push(nptr);

            nptr = nptr->left;

        }

    }

    cout << endl;

    return;

}

//Non recursive preorder tree traversal

template<typename T> void BST<T>::preorder_non_recursive(NODE<BT>* nptr)

{

    cout << endl;

    stack<NODE<BT>*> s;

    /*Root is NULL, nothing to do.*/

    if (!nptr)

        return;

    /*Push root*/

    s.push(nptr);

    while (!s.empty())

    {

        /*Pop the top element*/

        NODE<BT>* tmpPtr = s.top();

        cout << tmpPtr->data << "\t";

        s.pop();

        /*Go right before going left as we are using a stack.*/

        if (tmpPtr->right)

            s.push(tmpPtr->right);

        if (tmpPtr->left)

            s.push(tmpPtr->left);

    }

    cout << endl;

    return;

}

/*Non recursive postorder tree traversal. There are  two solutions of this traversal

  * 1.) using two stacks

  * 2.) using one stack

*/

template<typename T> void BST<T>::postorder_non_recursive(NODE<BT>* nptr)

{

    cout << endl;

    if (!nptr)

        return;

    stack<NODE<BT>*> stk1;

    stack<NODE<BT>*> stk2;

    /*Push root into stack stk1*/

    stk1.push(nptr);

    while (!stk1.empty())

    {

        /*Pop fropm sack stk1 and push it to stack stk2*/

        NODE<BT>* tmpPtr = stk1.top();

        stk2.push(tmpPtr);

        stk1.pop();

        /*Now push left child before right. Because when we push it back to

        stack stk2, the order will be correct.*/

        if (tmpPtr->left)

            stk1.push(tmpPtr->left);

        if (tmpPtr->right)

            stk1.push(tmpPtr->right);

    }

    /*Now stk2 has got all the nodes in postorder. We will just pop it one by

    one and print.*/

    while (!stk2.empty())

    {

        NODE<BT>* tmpPtr = stk2.top();

        stk2.pop();

        cout << tmpPtr->data << "\t";

    }

    cout << endl;

    return;

}

//Non recursive postorder tree trraversal using only one stack.

template<typename T> void BST<T>::postorder_non_recursive_1(NODE<BT>* nptr)

{

    if (!nptr)

        return;

    cout << endl;

    stack<NODE<BT>*> s;

    /*We will need current poionter to the node we are currently

    traversing and the pointer to the node we traversed previously.*/

    NODE<BT>* current = nptr;

    NODE<BT>* previous = NULL;

    s.push(current);

    while (!s.empty())

    {

        current = s.top();

        /*Traverse the tree down*/

        if (!previous || previous->left == current || previous->right == current)

        {

            if (current->left)

                s.push(current->left);

            else if (current->right)

                s.push(current->right);

            else

            {

                cout << current->data << "\t";

                s.pop();

            }

        }

        /*Traverse the tree up from the left*/

        else if (current->left == previous)

        {

            if (current->right)

                s.push(current->right);

            else

            {

                cout << current->data << "\t";

                s.pop();

            }

        }

        else if (current->right == previous)

        {

            cout << current->data << "\t";

            s.pop();

        }

        previous = current;

    }

    cout << endl;

    return;

}