#include #include // Formula for full binary trees: // nodes = 2^(depth + 1) - 1 namespace detail { template auto visit_before_helper(I depth, I label) -> void { std::cout << label << ' '; if (depth > 0) { // the left child is printed next, thus // we add 1 to the label visit_before_helper(depth - 1, label + 1); // the right child is printed after the left subtree, thus // we add 1 (right child) + the number of nodes in the left subtree to the label visit_before_helper(depth - 1, label + (1 << depth)); } } template auto visit_between_helper(I depth, I label) -> void { std::cout << label << ' '; if (depth > 0) { // the left subtree of the left child is printed before its label, thus // we subtract 1 (left child) + the number of nodes in the child's subtree from the label visit_between_helper(depth - 1, label - (1 << (depth - 1))); // the left subtree of the right child is printed before its label, thus // we add 1 (right child) + the number of nodes in the child's subtree to the label visit_between_helper(depth - 1, label + (1 << (depth - 1))); } } template auto visit_after_helper(I depth, I label) -> void { std::cout << label << ' '; if (depth > 0) { // the right subtree will be printed afterwards, thus // we subtract 1 (left child) + the number of nodes there from the label visit_after_helper(depth - 1, label - (1 << depth)); // the right child was the one printed before, thus // we subtract 1 from the label visit_after_helper(depth - 1, label - 1); } } } // namespace detail template auto visit_before(I depth) -> std::enable_if_t> { detail::visit_before_helper(depth, 0); } template auto visit_between(I depth) -> std::enable_if_t> { detail::visit_between_helper(depth, (1 << depth) - 1); } template auto visit_after(I depth) -> std::enable_if_t> { detail::visit_after_helper(depth, (2 << depth) - 2); } int main(int, char**) { std::cout << "Pre-Order: "; visit_before(3); std::cout << "\nIn-Order: "; visit_between(3); std::cout << "\nPost-Order: "; visit_after(3); std::cout << '\n'; return EXIT_SUCCESS; }

[Q&A] Traversal Order