Skip to content

Instantly share code, notes, and snippets.

@whoan
Last active November 11, 2019 19:12
Show Gist options
  • Save whoan/43ffc6f193cc9eb38845ed958f921710 to your computer and use it in GitHub Desktop.
Save whoan/43ffc6f193cc9eb38845ed958f921710 to your computer and use it in GitHub Desktop.
DFS traversals
class DFS {
enum Method {
PreOrder, InOrder, PostOrder
} method;
enum Direction {
LeftToRight, RightToLeft
} direction;
template <typename TreeNode>
DFS(TreeNode root, Method method, Direction direction=LeftToRight)
: method(method), direction(direction)
{
traverse(root);
}
template <typename TreeNode>
void visit(TreeNode node) {
std::cerr << node->data << " ";
}
template <typename TreeNode>
void traverse(TreeNode node) {
if (!node) {
return;
}
if (method == Method::PreOrder) {
visit(node);
}
traverse(direction == LeftToRight ? node->left : node->right);
if (method == Method::InOrder) {
visit(node);
}
traverse(direction == LeftToRight ? node->right : node->left);
if (method == Method::PostOrder) {
visit(node);
}
}
public:
template <typename TreeNode>
static void preOrder(TreeNode root) {
DFS dfs(root, DFS::PreOrder);
}
template <typename TreeNode>
static void inOrder(TreeNode root) {
DFS dfs(root, DFS::InOrder);
}
template <typename TreeNode>
static void postOrder(TreeNode root) {
DFS dfs(root, DFS::PostOrder);
}
template <typename TreeNode>
static void preOrderReverse(TreeNode root) {
DFS dfs(root, DFS::PreOrder, DFS::RightToLeft);
}
template <typename TreeNode>
static void inOrderReverse(TreeNode root) {
DFS dfs(root, DFS::InOrder, DFS::RightToLeft);
}
template <typename TreeNode>
static void postOrderReverse(TreeNode root) {
DFS dfs(root, DFS::PostOrder, DFS::RightToLeft);
}
};
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment