#include <iostream>

template <typename T>
struct Node {
    T value;
    Node<T> *left, *right, *next_sibling;
};

template <typename T>
void link_siblings(Node<T> *root) {
    //   * -> * <upper
    // /   \
    // * -> * <lower
    // ^ level_start
    Node<T> *upper = root, *lower = nullptr, *level_start = nullptr;
    while (upper) {
        for (auto child : {upper->left, upper->right}) {
            if (child) {
                if (lower) lower->next_sibling = child;
                else       level_start         = child;
                lower = child;
            }
        }

        if (upper->next_sibling) {
            upper = upper->next_sibling;
        } else {
            upper = level_start;
            level_start = lower = nullptr;
        }
    }
}

int main() {
    //        0
    //   1        4
    // 2   3         5
    constexpr int N = 6;
    Node<int> nodes[N];
    int lchildren[N] = {1,  2, -1, -1, -1, -1};
    int rchildren[N] = {4,  3, -1, -1,  5, -1};
    for (int i = 0; i < N; i++) {
        nodes[i].value = i;
        nodes[i].left = nodes[i].right = nodes[i].next_sibling = nullptr;
        if (lchildren[i] >= 0) nodes[i].left  = &nodes[lchildren[i]];
        if (rchildren[i] >= 0) nodes[i].right = &nodes[rchildren[i]];
    }
    link_siblings(&nodes[0]);
    for (int i = 0; i < N; i++) {
        auto sibling = nodes[i].next_sibling;
        int sibling_value = sibling ? (sibling->value) : -1;
        std::cout << nodes[i].value << " => " << sibling_value << "\n";
    }
    return 0;
}