Tree Traversal II¶

Title: Tree: Postorder Traversal
Link: https://www.hackerrank.com/challenges/tree-postorder-traversal

In the previous challenge we stated we would address several tree traversal methods with a single codebase. We therefore extend the latest solution to do it.

We will also make our StdTree a bit more generic as it will:

Take a typename T instead of simply taking int as the type for the nodes.
The visit function will also be a template parameter.

That will push us to implement SFINAE directly to check that:

The type T supports the operators <, == and !=, the ones we are using for different parts of the code to chose alternative actions.
The visit function type F can take a single T as a parameter.

Although we would be looking at implementing only a postorder traversal method, we will also add inorder, because we will use the pattern to improve our implementation.

The SFINAE checks for operator support follow this pattern.

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;

GitHub: 18-tree-traversal-ii/tree-traversal-ii-01.cpp:11:16

The visiting function check is also no stranger, with std::void_t and std::invoke_result taking the load of the work.

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;

GitHub: 18-tree-traversal-ii/tree-traversal-ii-01.cpp:37:42

All those small checks are wrapped in custom enable_if_xxx definitions and later applied to the corresponding functions.

Let us concentrate on the traversal methods. First the core or preorder

        fvisit(node); // preorder ... out root
        preorder(fvisit, left); // visit left
        preorder(fvisit, right); // visit right

GitHub: 18-tree-traversal-ii/tree-traversal-ii-01.cpp:64:66

And then postorder and inorder.

        postorder(fvisit, left); // visit left
        postorder(fvisit, right); // visit right
        fvisit(node); // postorder ... out root

GitHub: 18-tree-traversal-ii/tree-traversal-ii-01.cpp:74:76

        inorder(fvisit, left); // visit left
        fvisit(node); // inorder ... out root
        inorder(fvisit, right); // visit right

GitHub: 18-tree-traversal-ii/tree-traversal-ii-01.cpp:84:86

And the pattern emerges:

We recurse using the same method to the left and to the right
Only when the fvisit(node) call is executed changes
- preorder: before visiting the lower nodes
- postorder: after visiting the lower nodes
- inorder: after visiting the left lower nodes and before visiting the right lower ones

This means that we actually only move around the position of the fvisit(node) call and the rest is just a node visiting thing. That is our pattern to go for more.

Constexpressing the Traversals¶

With the aforementioned pattern we can apply our C++17 beloved if constexpr to choose where to place the fvisit call.

The external interfaces for the traversal methods will all rely on a single internal interface named visit.

    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); }

GitHub: 18-tree-traversal-ii/tree-traversal-ii-02.cpp:85:90

Each public method specializes visit with an internal enum that properly defines the names Pre, In and Post. That specialization is the key to let if constexpr place the fvisit(node) call.

    enum class Order { Pre, Post, In };

    template <Order order, typename F, typename = enable_if_fvisit<F, T>>
    auto visit(const F &fvisit, const T &node) const {
        if (node == NullTreeVal)
            return; // if empty ... will do nothing

        const auto &[left, right] = m_tree.at(node); // get children
        if constexpr (order == Order::Pre) fvisit(node); // pre -> root
        visit<order>(fvisit, left); // visit left
        if constexpr (order == Order::In) fvisit(node); // inorder -> root
        visit<order>(fvisit, right); // visit right
        if constexpr (order == Order::Post) fvisit(node); // post -> root
    }

GitHub: 18-tree-traversal-ii/tree-traversal-ii-02.cpp:58:71

As we know this generates as many different methods in the background as we invoke visit with different template parameters. But from a practical point of view we have implemented a single method capable of working as three different methods.

Futile Attempt At Performance¶

Now that we have proper external and internal interfaces, let us try to improve performance. It is probably going to be a futile attempt because we have a 10x performance difference. We will, however, introduce a small change to see if something changes. Recall that Bon Jovi sang: “The more things change the more they stay the same” and our performance is therefore doomed to stay the same.

In our solution we are using std::pair<int, int> (or <T, T> in the templated version) to hold the children and have then to access .first and .second to choose the left and right children node. But because std::pair can handle different types, there has to be a lot of machinery to account for that. Let us therefore simplify that: we will use std::array<T, 2> to have a fixed array size assignment and no type magic.

We introduce an enum to properly access Node::Left and Node::Right, although we only need to keep the initial reference to the real root as a child of the virtual root. This is so because we will still use Structured Bindings and the comparison < of T types when inserting to choose the position.

Here is how the Children now look like.

template <typename T = int, typename = enable_if_T_ops<T>>
class StdTree {
    static constexpr auto NullTreeVal = T{};
    enum Node { Left = 0, Right = 1, Total = 2 };
    using Children = std::array<T, Node::Total>;
    static constexpr auto NullChildren = Children{NullTreeVal, NullTreeVal};

GitHub: 18-tree-traversal-ii/tree-traversal-ii-03.cpp:48:53

Accessing both the left and right node at the same time does not change.

    template <Order order, typename F, typename = enable_if_fvisit<F, T>>
    auto visit(const F &fvisit, const T &node) const {
        if (node == NullTreeVal)
            return; // if empty ... will do nothing

        const auto &[left, right] = m_tree.at(node); // get children

GitHub: 18-tree-traversal-ii/tree-traversal-ii-03.cpp:61:66

But we put the operator [] of std::array to good use when selecting the child to insert things into (or create a new node)

    void insert(const T &data, const T &node) {
        auto &child = m_tree.at(node)[not (data < node)];

GitHub: 18-tree-traversal-ii/tree-traversal-ii-03.cpp:74:75

Let us check if the performance has actually improved.

$ make 03 test05 rep10000 o2
g++ -std=c++17 -DREPS=10000 -o build/tree-traversal-ii-03 tree-traversal-ii-03.cpp
0.394339

Not really, i.e., no, there has been no improvement at all, when considering “orders or magnitude”. It would really have been a miracle, had it happened. Let us think about it: an std::unordered_map is based on a hash table and that means that we are implementing a container, a tree, on top of another container. An std::map is for example implemented atop a red-black tree and that is already a good indication that implementing a tree on top of another tree (or a similar structure) is going to hurt the performance of our solution.

But if we compare that timing with the timing of our 01 solution (still std::pair based) there is an average advantage of 20 milliseconds for the test with 10,000 repetitions. Not much, but it shows that std::pair is giving us a small leading edge.

Listings¶

Let us list the code of the three solutions we presented above.

T-Template Map-Based Tree - 01¶

#include <algorithm> // std::copy_n
#include <chrono> // std::chrono::xx
#include <iostream> // std::cout/cin
#include <iterator> // std::istream/ostream_iterator
#include <unordered_map> // std::unordered_map
#include <utility> // std::pair
#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 {
    static constexpr auto NullTreeVal = T{};
    using Children = std::pair<T, T>;
    static constexpr auto NullChildren = Children{NullTreeVal, NullTreeVal};

    // init tree with empty virtual root
    std::unordered_map<T, Children> m_tree{{NullTreeVal, NullChildren}};
    const T &m_root = m_tree.at(NullTreeVal).second; // ref 2 real root

    template <typename F, typename = enable_if_fvisit<F, T>>
    auto preorder(const F &fvisit, const T &node) const {
        if (node == NullTreeVal)
            return; // if empty ... will do nothing

        const auto &[left, right] = m_tree.at(node); // get children
        fvisit(node); // preorder ... out root
        preorder(fvisit, left); // visit left
        preorder(fvisit, right); // visit right
    }
    template <typename F, typename = enable_if_fvisit<F, T>>
    auto postorder(const F &fvisit, const T &node) const {
        if (node == NullTreeVal)
            return; // if empty ... will do nothing

        const auto &[left, right] = m_tree.at(node); // get children
        postorder(fvisit, left); // visit left
        postorder(fvisit, right); // visit right
        fvisit(node); // postorder ... out root
    }
    template <typename F, typename = enable_if_fvisit<F, T>>
    auto inorder(const F &fvisit, const T &node) const {
        if (node == NullTreeVal)
            return; // if empty ... will do nothing

        const auto &[left, right] = m_tree.at(node); // get children
        inorder(fvisit, left); // visit left
        fvisit(node); // inorder ... out root
        inorder(fvisit, right); // visit right
    }

    void insert(const T &data, const T &node) {
        auto &child = data < node ? m_tree[node].first : m_tree[node].second;
        if (child != NullTreeVal)
            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 { preorder(fvisit, m_root); }
    template <typename F, typename = enable_if_fvisit<F, T>>
    auto postorder(const F &fvisit) const { postorder(fvisit, m_root); }
    template <typename F, typename = enable_if_fvisit<F, T>>
    auto inorder(const F &fvisit) const { inorder(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.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); //

    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;
}

GitHub: 18-tree-traversal-ii/tree-traversal-ii-01.cpp

Constexpr Traversals - 02¶

#include <algorithm> // std::copy_n
#include <iostream> // std::cout/cin
#include <iterator> // std::istream/ostream_iterator
#include <unordered_map> // std::unordered_map
#include <utility> // std::pair
#include <chrono> // std::chrono::xx
#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 {
    static constexpr auto NullTreeVal = T{};
    using Children = std::pair<T, T>;
    static constexpr auto NullChildren = Children{NullTreeVal, NullTreeVal};

    // init tree with empty virtual root
    std::unordered_map<T, Children> m_tree{{NullTreeVal, NullChildren}};
    const T &m_root = m_tree.at(NullTreeVal).second; // ref 2 real root

    enum class Order { Pre, Post, In };

    template <Order order, typename F, typename = enable_if_fvisit<F, T>>
    auto visit(const F &fvisit, const T &node) const {
        if (node == NullTreeVal)
            return; // if empty ... will do nothing

        const auto &[left, right] = m_tree.at(node); // get children
        if constexpr (order == Order::Pre) fvisit(node); // pre -> root
        visit<order>(fvisit, left); // visit left
        if constexpr (order == Order::In) fvisit(node); // inorder -> root
        visit<order>(fvisit, right); // visit right
        if constexpr (order == Order::Post) fvisit(node); // post -> root
    }

    void insert(const T &data, const T &node) {
        auto &child = data < node ? m_tree[node].first : m_tree[node].second;
        if (child != NullTreeVal)
            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.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); //

    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;
}

GitHub: 18-tree-traversal-ii/tree-traversal-ii-02.cpp

Removing std::pair - 03¶

#include <algorithm> // std::copy_n
#include <array> // std::array
#include <iostream> // std::cout/cin
#include <iterator> // std::istream/ostream_iterator
#include <unordered_map> // std::unordered_map
#include <chrono> // std::chrono::xx
#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 {
    static constexpr auto NullTreeVal = T{};
    enum Node { Left = 0, Right = 1, Total = 2 };
    using Children = std::array<T, Node::Total>;
    static constexpr auto NullChildren = Children{NullTreeVal, NullTreeVal};

    // init tree with empty virtual root
    std::unordered_map<T, Children> m_tree{{NullTreeVal, NullChildren}};
    const T &m_root = m_tree.at(NullTreeVal)[Node::Right]; // ref 2 real root

    enum class Order { Pre, Post, In };

    template <Order order, typename F, typename = enable_if_fvisit<F, T>>
    auto visit(const F &fvisit, const T &node) const {
        if (node == NullTreeVal)
            return; // if empty ... will do nothing

        const auto &[left, right] = m_tree.at(node); // get children
        if constexpr (order == Order::Pre) fvisit(node); // pre -> root
        visit<order>(fvisit, left); // visit left
        if constexpr (order == Order::In) fvisit(node); // inorder -> root
        visit<order>(fvisit, right); // visit right
        if constexpr (order == Order::Post) fvisit(node); // post -> root
    }

    void insert(const T &data, const T &node) {
        auto &child = m_tree.at(node)[not (data < node)];
        if (child != NullTreeVal)
            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.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); //

    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;
}

GitHub: 18-tree-traversal-ii/tree-traversal-ii-03.cpp

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;
}

GitHub: 18-tree-traversal-ii/tree-traversal-ii-91.cpp