# Populating Next Right Pointers in Each Node II

Jan 5th, 2021
1,071
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. /*
2. // Definition for a Node.
3. class Node {
4. public:
5.     int val;
6.     Node* left;
7.     Node* right;
8.     Node* next;
9.
10.     Node() : val(0), left(NULL), right(NULL), next(NULL) {}
11.
12.     Node(int _val) : val(_val), left(NULL), right(NULL), next(NULL) {}
13.
14.     Node(int _val, Node* _left, Node* _right, Node* _next)
15.         : val(_val), left(_left), right(_right), next(_next) {}
16. };
17. */
18.
19. class Solution {
20. public:
21.
22.
23.     Node* connect(Node* root) {
24.         if(!root)   return root;
25.         root->next = nullptr;
26.         Node *parentLeftMost = root;
27.         //parent level is sorted
28.
29.         while(1){
30.             while(parentLeftMost && !parentLeftMost->left && !parentLeftMost->right){
31.                 parentLeftMost = parentLeftMost->next;
32.             }
33.             if(!parentLeftMost){
34.                 //i.e there is no next level
35.                 return root;
36.             }
37.             Node *upcomingParentLeftMost = parentLeftMost->left ? parentLeftMost->left : parentLeftMost->right;  //refers to the leftmost node of next level. Will be the next parentLeftMost
38.
39.             Node *tempP = parentLeftMost;
40.             Node *tempC = upcomingParentLeftMost;
41.             while(1){
42.
43.                 Node *toAttach = nullptr;
44.                 if(tempP->right != nullptr && tempP->right!= tempC){
45.                    toAttach = tempP->right;
46.                 }
47.                 else{
48.                     while(tempP->next != nullptr && toAttach == nullptr){
49.                         tempP = tempP->next;
50.                         toAttach = tempP->left ? tempP->left : tempP->right;
51.                     }
52.                 }
53.                 tempC->next = toAttach;
54.                 tempC = tempC->next;
55.                 if(tempC == nullptr){
56.                     parentLeftMost = upcomingParentLeftMost;
57.                     break;
58.                 }
59.             }
60.         }
61.     }
62. };