Tree Traversal III¶
Title: Tree: Inorder Traversal
Link: https://www.hackerrank.com/challenges/tree-inorder-traversal
Let us use the third of the traversal methods, inorder, to fix our design, given that we cannot really fix the performance.
Yes, we need to fix a basic design flaw. When we first addressed the tree traversal problem we used int{} (i.e., 0) to indicate that a node is a null node. This was not a problem for our solution because we know that problem values will be > 0.
The next design used typename T as the type and T{} as the null value. And this is simply the error repeating itself.
Let us therefore use a feature of C++17 that we have yet not explored: std::optional<T>. It is a class that manages a value of type T but may actually not contain any value. And that is what will use to have a real null value: an std::optional that contains no value.
That is, in fact, the value std::nullopt a constexpr value of type std::nullopt_t, a value that we will obtain by simply creating an empty std::optional<T>.
This is how we now define the data structure of our tree.
template <typename T = int, typename = enable_if_T_ops<T>>
class StdTree {
using TNode = std::optional<T>; // out real type is now the optional<T>
static constexpr auto NullTreeVal = TNode{}; // holds std::nullopt
enum Node { Left = 0, Right = 1, Total = 2 };
using Children = std::array<TNode, Node::Total>;
static constexpr auto NullChildren = Children{{}}; // two std::nullopt
// init tree with virtual root with empty children
std::unordered_map<TNode, Children> m_tree{{NullTreeVal, NullChildren}};
const TNode &m_root = m_tree.at(NullTreeVal)[Node::Right]; // real root ref
The tree does still take T as the type, but we use and store TNode which is defined as std::optional<T>. A simple substitution and we suddenly have a real null value, because our NullTreeVal is now holding a constexpr empty std::optional<T>, i.e. an std::nullopt as explained above.
The only small drawback is that we need an extra step to get the value out of our std::optional<T> and that is: using the operator * as is we were dereferencing a pointer or an iterator. However, we only need that when calling the visiting function fvisit.
Notice that the only change is the use of *node in fvisit(*node).
template <Order order, typename F, typename = enable_if_fvisit<F, T>>
auto visit(const F &fvisit, const TNode &node) const {
if (not node)
return; // if empty ... will do nothing
const auto &[left, right] = m_tree.at(node); // get children
if constexpr (order == Order::Pre) fvisit(*node); // pre
visit<order>(fvisit, left); // visit left
if constexpr (order == Order::In) fvisit(*node); // inorder
visit<order>(fvisit, right); // visit right
if constexpr (order == Order::Post) fvisit(*node); // post
}
On the other hand, we no longer need to compare against a NullTreeVal as we did before, because our std::optional<T> will evaluate to false if no value is contained, i.e., an std::nullopt is contained instead of an instance of type T. But we still use it as a key for the virtual root.
Given that we have added another layer of indirection, let us check the timing of this solution to see if we have gone yet another order of magnitude away from the optimal solution.
The timing of our std::optional solution
$ make 01 rep10000 test05 o2
g++ -std=c++17 -DREPS=10000 -O2 -o build/tree-traversal-iii-01 tree-traversal-iii-01.cpp
0.497966
And the one of the <std::unique_ptr>-based tree
$ make 01 rep10000 test05 o2
g++ -std=c++17 -DREPS=10000 -O2 -o build/tree-traversal-iii-01 tree-traversal-iii-01.cpp
0.0948075
We are slightly above 5x, the multiplier we had when we first measured performance against a pointer-based tree. Still in that ballpark, which means that using std::optional is not really a headache and has improved our code by letting us use the full spectrum of values of the type T. Recall that we were before blocking int{} or T{} as the values to indicate a null node, voiding the presence of those values as valid data in a node.
Listings¶
Optional-Based Map Tree - 01¶
#include <algorithm> // std::copy_n
#include <array> // std::array
#include <chrono> // std::chrono::xx
#include <iostream> // std::cout/cin
#include <iterator> // std::istream/ostream_iterator
#include <optional> // std::optional
#include <unordered_map> // std::unordered_map
#include <vector> // std::vector
#include <type_traits> // std::enable_if, std::invoke_result, std::void_t
// SFINAE for the Tree Type (operator support)
template<typename, typename = void>
constexpr bool op_lt_v = false;
template<typename T>
constexpr bool
op_lt_v<T, std::void_t<decltype(std::declval<T>() < std::declval<T>())>> = true;
template<typename, typename = void>
constexpr bool op_ne_v = false;
template<typename T>
constexpr bool
op_ne_v<T, std::void_t<decltype(std::declval<T>() != std::declval<T>())>> = true;
template<typename, typename = void>
constexpr bool op_eq_v = false;
template<typename T>
constexpr bool
op_eq_v<T, std::void_t<decltype(std::declval<T>() == std::declval<T>())>> = true;
template <typename T>
using enable_if_T_ops =
std::enable_if_t<op_lt_v<T> and op_ne_v<T> and op_eq_v<T>>;
// SFINAE: Visiting Function
template<typename, typename, typename = void>
constexpr bool f_visit = false;
template<typename F, typename T>
constexpr bool
f_visit<F, T, std::void_t<std::invoke_result_t<F, T>>> = true;
template <typename F, typename T>
using enable_if_fvisit = std::enable_if_t<f_visit<F, T>>;
// Tree Class
template <typename T = int, typename = enable_if_T_ops<T>>
class StdTree {
using TNode = std::optional<T>; // out real type is now the optional<T>
static constexpr auto NullTreeVal = TNode{}; // holds std::nullopt
enum Node { Left = 0, Right = 1, Total = 2 };
using Children = std::array<TNode, Node::Total>;
static constexpr auto NullChildren = Children{{}}; // two std::nullopt
// init tree with virtual root with empty children
std::unordered_map<TNode, Children> m_tree{{NullTreeVal, NullChildren}};
const TNode &m_root = m_tree.at(NullTreeVal)[Node::Right]; // real root ref
enum class Order { Pre, Post, In };
template <Order order, typename F, typename = enable_if_fvisit<F, T>>
auto visit(const F &fvisit, const TNode &node) const {
if (not node)
return; // if empty ... will do nothing
const auto &[left, right] = m_tree.at(node); // get children
if constexpr (order == Order::Pre) fvisit(*node); // pre
visit<order>(fvisit, left); // visit left
if constexpr (order == Order::In) fvisit(*node); // inorder
visit<order>(fvisit, right); // visit right
if constexpr (order == Order::Post) fvisit(*node); // post
}
void insert(const T &data, const TNode &node) {
auto &child = m_tree.at(node)[not (data < node)];
if (child)
return insert(data, child); // already in tree, go deeper
// not in tree, add it with default empty children
m_tree[child = data] = NullChildren; // set target (left or right ref)
}
public:
// start always with the virtual root value
auto insert(const T &data) { insert(data, NullTreeVal); }
// start with the reference to the real root
template <typename F, typename = enable_if_fvisit<F, T>>
auto preorder(const F &fvisit) const { visit<Order::Pre>(fvisit, m_root); }
template <typename F, typename = enable_if_fvisit<F, T>>
auto inorder(const F &fvisit) const { visit<Order::In>(fvisit, m_root); }
template <typename F, typename = enable_if_fvisit<F, T>>
auto postorder(const F &fvisit) const { visit<Order::Post>(fvisit, m_root); }
};
// Solution Function
template <typename I, typename F>
auto
solution(I in, F fout, int size) {
auto tree = StdTree{};
while(size--)
tree.insert(*in++);
tree.inorder(fout);
}
// Main
int
main(int, char *[]) {
auto in = std::istream_iterator<int>{std::cin}; // input iterator
auto out = std::ostream_iterator<int>{std::cout, " "}; // out iter
auto oerr = std::ostream_iterator<double>(std::cerr, "\n");
auto reps = 1;
#ifdef REPS
reps = REPS;
#endif
auto t = *in++;
auto v = std::vector<int>(t);
auto vin = v.begin();
std::copy_n(in, t, vin); //
auto fout = [&out](const auto &x){ out = x; };
auto fakeout = [](const auto &){};
auto start = std::chrono::steady_clock::now();
solution(vin, fout, t); // to match expected output
while(--reps)
solution(vin, fakeout, t); // extra rounds output nothing
auto stop = std::chrono::steady_clock::now();
auto elapsed_seconds = std::chrono::
duration_cast<std::chrono::duration<double>>(stop - start).count();
oerr = elapsed_seconds;
return 0;
}
UniquePtr T-Templated/Contsexpress Traversals - 91¶
#include <algorithm> // std::copy_n
#include <chrono> // std::chrono::xx
#include <iostream> // std::cout/cin
#include <iterator> // std::istream/ostream_iterator
#include <memory> // std::unique_ptr
#include <vector> // std::vector
template <class T = int>
class UniquePtrTree {
struct Node {
T m_data;
using NodePtr = std::unique_ptr<Node>;
NodePtr left, right;
Node(const T &data) : m_data{data} {};
auto static create(const T &d) { return std::make_unique<Node>(d); }
};
using NodePtr = typename Node::NodePtr;
NodePtr m_root;
auto insert(const T &data, NodePtr &node) {
if(not node) {
node = Node::create(data);
return;
}
insert(data, data < node->m_data ? node->left : node->right);
}
enum class Order { Pre, Post, In };
template <Order order, typename F>
auto visit(const F &fvisit, const NodePtr &node) const {
if (not node)
return;
if constexpr (order == Order::Pre) fvisit(node->m_data); // pre
visit<order>(fvisit, node->left); // visit left
if constexpr (order == Order::In) fvisit(node->m_data); // inorder
visit<order>(fvisit, node->right); // visit right
if constexpr (order == Order::Post) fvisit(node->m_data); // post
}
public:
auto insert(const T &data) { insert(data, m_root); };
template <typename F>
auto preorder(const F &fvisit) const { visit<Order::Pre>(fvisit, m_root); }
template <typename F>
auto postorder(const F &fvisit) const { visit<Order::Post>(fvisit, m_root); }
template <typename F>
auto inorder(const F &fvisit) const { visit<Order::In>(fvisit, m_root); }
};
template <typename I, typename F>
auto
solution(I in, F fout, int size) {
auto tree = UniquePtrTree{};
while(size--)
tree.insert(*in++);
tree.postorder(fout);
}
// Main
int
main(int, char *[]) {
auto in = std::istream_iterator<int>{std::cin}; // input iterator
auto out = std::ostream_iterator<int>{std::cout, " "}; // out iter
auto oerr = std::ostream_iterator<double>(std::cerr, "\n");
auto reps = 1;
#ifdef REPS
reps = REPS;
#endif
auto t = *in++;
auto v = std::vector<int>(t);
auto vin = v.begin();
std::copy_n(in, t, vin); // vin is not invalidated
auto fout = [&out](const auto &x){ out = x; };
auto fakeout = [](const auto &){};
auto start = std::chrono::steady_clock::now();
solution(vin, fout, t); // to match expected output
while(--reps)
solution(vin, fakeout, t); // extra rounds for timing, no output
auto stop = std::chrono::steady_clock::now();
auto elapsed_seconds = std::chrono::
duration_cast<std::chrono::duration<double>>(stop - start).count();
oerr = elapsed_seconds;
return 0;
}