Skip to content

Instantly share code, notes, and snippets.

@santa4nt
Last active August 29, 2015 14:27
Show Gist options
  • Save santa4nt/e2b4c1267cbad5de0d08 to your computer and use it in GitHub Desktop.
Save santa4nt/e2b4c1267cbad5de0d08 to your computer and use it in GitHub Desktop.
Binary tree traversal algorithms, without recursion.
#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;
}
#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__
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment