  #include <iostream>

#include <vector>

#include <unordered_map>

using namespace std;

// structure to store a node

struct Node

{

int data;

Node *left, *right, *next;

// constructor

Node(int data)

{

this->data = data;

this->left = this->right = this->next = nullptr;

}

};

// Function to print a given

{

{

cout << head->data << ” -> “;

}

cout << “null” << ‘n’;

}

// Recursive function to find the first node in next of the root node

Node* findNextNode(Node* root)

{

// base case

if (root == nullptr || root->next == nullptr)

return nullptr;

// if left child of root’s next node exists, return it

if (root->next->left)

return root->next->left;

// if right child of root’s next node exists, return it

if (root->next->right)

return root->next->right;

// if root’s next node is a leaf node, recur for root’s next node

return findNextNode(root->next);

}

// Function to traverse the in pre-order fashion and

// insert all nodes into the map corresponding to their level

void linkNodes(Node *root, int level, auto &map)

{

// base case: empty subtree

if (root == nullptr)

return;

// insert the current node and level information into the map

map[level].push_back(root);

// recurse for left and right subtree by increasing level by 1

linkNodes(root->left, level + 1, map);

linkNodes(root->right, level + 1, map);

}

// Function to nodes in each level of a binary tree

// using next pointer

{

// create an empty map to store nodes present at each level

// from left to right

unordered_map<int, vector<Node*>> map;

// traverse the tree in pre-order fashion and fill map

// iterate through the map and for each level,

// set next node for every node in it

for (auto it: map)

{

Node* prev = nullptr;

for (Node* curr: it.second)

{

if (prev)

prev->next = curr;

prev = curr;

}

prev->next = nullptr;

}

}

// main function

int main()

{

/* Construct below Tree

1

/

2     3

/

4   5     6

/

7     8

*/

Node* root = new Node(1);

root->left = new Node(2);

root->right = new Node(3);

root->left->left = new Node(4);

root->left->right = new Node(5);

root->right->right = new Node(6);

root->left->left->right = new Node(7);

root->right->right->left = new Node(8);

// link nodes at the same level

// print the nodes

Node* node = root;

while (node)

{

// print current level

printList(node);

// find leftmost node of the next level

if (node->left)

node = node->left;

else if (node->right)

node = node->right;

else

node = findNextNode(node);

}

return 0;

}

SHARE