Binary tree traversal algorithms, without recursion.

traversal.cc

#include <stack>
#include <vector>
#include <memory>
#include <functional>
#include <iostream>

#include "tree.hpp"


using namespace std;


template <typename T>
using VisitorFunc = function<void(NodePtr<T>)>;


template <typename T>
void traverse_in_order(NodePtr<T> root, VisitorFunc<T> visit)
{
    /** the recursive algorithm:
    for (;;)
    {
        if (root == nullptr) break;
        traverse_in_order(root->left());
        cout << root->key() << " ";
        traverse_in_order(root->right());
        break;
    }
    **/

    stack<NodePtr<T>> st;
    NodePtr<T> node = root;

    // first, go all the way to the left-most node, pushing nodes encountered onto the stack
    for (; node != nullptr; node = node->left())
    {
        st.push(node);
    }

    while (!st.empty())
    {
        node = st.top(); st.pop();
        visit(node);
        // if this node has a right child, push it--and all its left (ONLY!) descendants--onto
        // the stack because this right child's most-left grandchild has to be visited next
        for (node = node->right(); node != nullptr; node = node->left())
        {
            st.push(node);
        }
    }
}

template <typename T>
void traverse_pre_order(NodePtr<T> root, VisitorFunc<T> visit)
{
    /** the recursive algorithm:
    for (;;)
    {
        if (root == nullptr) break;
        cout << root->key() << " ";
        traverse_pre_order(root->left());
        traverse_pre_order(root->right());
        break;
    }
    **/

    // straight-up DFS recursive call emulation
    stack<NodePtr<T>> st;
    st.push(root);

    while (!st.empty())
    {
        NodePtr<T> node = st.top(); st.pop();
        visit(node);
        if (node->right() != nullptr)
        {
            st.push(node->right());
        }
        if (node->left() != nullptr)
        {
            st.push(node->left());
        }
    }
}

template <typename T>
void traverse_post_order(NodePtr<T> root, VisitorFunc<T> visit)
{
    /** the recursive algorithm:
    for (;;)
    {
        if (root == nullptr) break;
        traverse_post_order(root->left());
        traverse_post_order(root->right());
        cout << root->key() << " ";
        break;
    }
    **/

    vector<T> result;       // stores the post-order keys

    // this is the most complex algorithm to not involve recursion:
    // two stacks are used: one to be used in a slightly modified pre-order manner,
    // and the second one to dump nodes "visited"/popped from the first stack
    stack<NodePtr<T>> st_temp;
    stack<NodePtr<T>> st_order;

    st_temp.push(root);

    while (!st_temp.empty())
    {
        NodePtr<T> node = st_temp.top(); st_temp.pop();
        st_order.push(node);        // the first node popped from the "pre-order" stack goes first
                                    // in the post-order stack, so that it will be popped last eventually
        // unlike conventional pre-order operation, we push the left child first
        if (node->left() != nullptr)
        {
            st_temp.push(node->left());
        }
        // so that in the next iteration, the right child gets "visited" and pushed in the post-order stack,
        // so that when the post-order stack gets popped, the right child gets popped AFTER the left child
        if (node->right() != nullptr)
        {
            st_temp.push(node->right());
        }
    }

    // the second stack now contains the nodes in post-order, when popped
    while (!st_order.empty())
    {
        visit(st_order.top());
        st_order.pop();
    }
}


int main()
{
    NodePtr<int> n0( Node<int>::create_node(0) );
    NodePtr<int> n1( Node<int>::create_node(1) );
    NodePtr<int> n2( Node<int>::create_node(2) );
    NodePtr<int> n3( Node<int>::create_node(3) );
    NodePtr<int> n4( Node<int>::create_node(4) );
    NodePtr<int> n5( Node<int>::create_node(5) );
    NodePtr<int> n6( Node<int>::create_node(6) );
    NodePtr<int> n7( Node<int>::create_node(7) );
    NodePtr<int> n8( Node<int>::create_node(8) );
    NodePtr<int> n9( Node<int>::create_node(9) );

    // construct a balanced BST rooted at '5'

    n0->set_right(n1);
    n3->set_right(n4);
    n6->set_right(n7);
    n2->set_left(n0);
    n2->set_right(n3);
    n8->set_left(n6);
    n8->set_right(n9);
    n5->set_left(n2);
    n5->set_right(n8);

    NodePtr<int> root = n5;

    // in-order:    0 1 2 3 4 5 6 7 8 9
    // pre-order:   5 2 0 1 3 4 8 6 7 9
    // post-order:  1 0 4 3 2 7 6 9 8 5
    
    vector<int> ordered;
    VisitorFunc<int> visit = [&ordered](NodePtr<int> node) -> void
    {
        ordered.push_back(node->key());
    };

    traverse_in_order(root, visit);
    cout << "in-order:\t";
    for (int i : ordered)
    {
        cout << i << " ";
    }
    cout << endl;

    ordered.clear();
    traverse_pre_order(root, visit);
    cout << "pre-order:\t";
    for (int i : ordered)
    {
        cout << i << " ";
    }
    cout << endl;

    ordered.clear();
    traverse_post_order(root, visit);
    cout << "post-order:\t";
    for (int i : ordered)
    {
        cout << i << " ";
    }
    cout << endl;

    return 0;
}

tree.hpp

#ifndef __TREE_HPP_DEFINED__
#define __TREE_HPP_DEFINED__

#include <memory>


template <typename T>
class Node;

template <typename T>
using NodePtr = std::shared_ptr<Node<T>>;

template <typename T>
class Node
{
private:

    T _key;
    NodePtr<T> _left;
    NodePtr<T> _right;

protected:

    Node(T key, NodePtr<T> left = nullptr, NodePtr<T> right = nullptr);

public:
    
    static NodePtr<T> create_node(T key, NodePtr<T> left = nullptr, NodePtr<T> right = nullptr);

    inline T key() const;
    inline NodePtr<T> left() const;
    inline NodePtr<T> right() const;

    inline void set_left(NodePtr<T> left);
    inline void set_right(NodePtr<T> right);

};


template <typename T>
/*static*/ NodePtr<T> Node<T>::create_node(T key, NodePtr<T> left, NodePtr<T> right)
{
    return NodePtr<T>( new Node(key, left, right) );
}

template <typename T>
Node<T>::Node(T key, NodePtr<T> left, NodePtr<T> right)
    : _key(key)
    , _left(left)
    , _right(right)
{
}

template <typename T>
T Node<T>::key() const
{
    return _key;
}

template <typename T>
NodePtr<T> Node<T>::left() const
{
    return _left;
}

template <typename T>
NodePtr<T> Node<T>::right() const
{
    return _right;
}

template <typename T>
void Node<T>::set_left(NodePtr<T> left)
{
    _left = left;
}

template <typename T>
void Node<T>::set_right(NodePtr<T> right)
{
    _right = right;
}

#endif//__TREE_HPP_DEFINED__