fork download
copy 
  1. #include <iostream>
  2. using namespace std;
  3.  
  4. // Data structure to store a Binary Tree node
  5. struct Node
  6. {
  7.     int data;
  8.     Node *left, *right, *next;
  9.  
  10.     // constructor
  11.     Node(int data)
  12.     {
  13.         this->data = data;
  14.         this->left = this->right = this->next = nullptr;
  15.     }
  16. };
  17.  
  18. // Function to print a given linked list
  19. void printList(Node* head)
  20. {
  21.     while (head)
  22.     {
  23.         cout << head->data << " -> ";
  24.         head = head->next;
  25.     }
  26.  
  27.     cout << "null" << '\n';
  28. }
  29.  
  30. // Function to perform inorder traversal of a binary tree where nodes
  31. // at the same level are linked together in the form of a linked list
  32. void inorder(Node* root)
  33. {
  34.     if (root == nullptr)
  35.         return;
  36.  
  37.     inorder(root->left);
  38.  
  39.     // print current node and its next node
  40.     cout << root->data << "->";
  41.     if (root->next)
  42.         cout << root->next->data << '\n';
  43.     else
  44.         cout << "null" << '\n';
  45.  
  46.     inorder(root->right);
  47. }
  48.  
  49. // Iterative function to find the first node in next level of the root node
  50. Node* findNextNode(Node* root)
  51. {
  52.     Node* node = root->next;
  53.     while (node)
  54.     {
  55.         // if left child of root's next node exists, return it
  56.         if (node->left)
  57.             return node->left;
  58.  
  59.         // if right child of root's next node exists, return it
  60.         if (node->right)
  61.             return node->right;
  62.  
  63.         // if root's next node is a leaf node, recur for root's next node        
  64.         node = node->next;
  65.     }
  66.  
  67.     // all nodes in current level are leaf nodes
  68.     return nullptr;
  69. }
  70.  
  71. // Iterative function to link nodes present in each level of a binary tree
  72. // in the form of a linked list
  73. void linkNodes(Node* root)
  74. {
  75.     // base case
  76.     if (root == nullptr)
  77.         return;
  78.  
  79.     // update next pointer of binary tree nodes level by level from top to bottom
  80.     while (root)
  81.     {
  82.         // get leftmost node in the current level
  83.         Node* node = root;
  84.  
  85.         // link all nodes at the current level
  86.         while (node)
  87.         {
  88.             // update the next pointer of root's left child to root's right child
  89.             // if right child doesn't exist, link it to first node in the next level
  90.             if (root->left) {
  91.                 root->left->next = (root->right)? root->right: findNextNode(root);
  92.             }
  93.  
  94.             // update the next pointer of root's right child to first node
  95.             // in the next level
  96.             if (root->right) {
  97.                 root->right->next = findNextNode(root);
  98.             }
  99.  
  100.             // advance to the next node in same level
  101.             node = node->next;
  102.         }
  103.  
  104.         // find leftmost node of the next level for next iteration
  105.         if (root->left)
  106.             root = root->left;
  107.         else if (root->right)
  108.             root = root->right;
  109.         else
  110.            root = findNextNode(root);
  111.     }
  112. }
  113.  
  114. // main function
  115. int main()
  116. {
  117.     /* Construct below Tree
  118.            1
  119.          /   \
  120.         2     3
  121.        / \     \
  122.       4   5     6
  123.        \       /
  124.         7     8
  125.     */
  126.  
  127.     Node* root = new Node(1);
  128.     root->left = new Node(2);
  129.     root->right = new Node(3);
  130.     root->left->left = new Node(4);
  131.     root->left->right = new Node(5);
  132.     root->right->right = new Node(6);
  133.     root->left->left->right = new Node(7);
  134.     root->right->right->left = new Node(8);
  135.  
  136.     // link nodes at the same level
  137.     linkNodes(root);
  138.  
  139.     // print the nodes
  140.     Node* node = root;
  141.     while (node)
  142.     {
  143.         // print current level
  144.         printList(node);
  145.  
  146.         // find leftmost node of the the next level
  147.         if (node->left)
  148.             node = node->left;
  149.         else if (node->right)
  150.             node = node->right;
  151.         else
  152.             node = findNextNode(node);
  153.     }
  154.  
  155.     // inorder(root);
  156.     return 0;
  157. }
Success #stdin #stdout 0s 15240KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1 -> null
2 -> 3 -> null
4 -> 5 -> 6 -> null
7 -> 8 -> null
https://ideone.com/1i5oGn
Link nodes present in each level of a binary tree in the form of a linked list
language:
C++14 (gcc 8.3)
created:
5 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!