C++ || 5 lines code || Very Easy || DFS || Simple || Explanation
This solution implements a recursive function - it takes a node, connects the NEXT pointers of it\'s left & right children, and repeats the process for the chil
This solution implements a recursive function - it takes a node, connects the NEXT pointers of it\'s left & right children, and repeats the process for the children. So the algorithm is :\nFor each non-leaf node, we do -\n(1) NEXT of Left child is pointed to Right child. Easy.\n(2) NEXT of Right child is pointed to NEXT node in the same level (i.e., parent\'s NEXT\'s left child).\n\nLet\'s consider the below example. Assume we are at the node "2".\n```\n\t\t\t\t   1\nwe are here\t=>   2 -> 3\n\t\t\t   3  4  5  6\n```\n\nSince we\'re at 2, we would already have our NEXT pointer pointing to the node 3 (should have been done at node 1).\nNow, we need to correctly set NEXT pointers of our children, i.e, 3 and 4. We follow the said algorithm here.\nStep 1 : 3\'s NEXT pointer should simply be set to 4.\nStep 2 : We know 4\'s NEXT pointer should now be set to 5. How do we do that? Remember we have 2\'s NEXT set to 3 already? We\'re going to use that to get reference of 3, and then reference of 5 - then we just use it! 4\'s NEXT is set to 2\'s NEXT\'s left, which is 5.\n\nSo the tree now becomes -\n\n```\n\t\t\t\t      1\nwe are here\t=>    2   ->   3\n\t\t\t   3 -> 4 -> 5    6\n```\n\nWe repeat this process until all NEXT nodes are set. \n\nIn case of last node of a level (for ex: 6), we don\'t have NEXT of our parent (3) anyway, so it\'s defaulted to NULL as required already.\nFor leaf nodes, we don\'t have children to set so we return.\n\n\nSolution Code in C++ \n```\nNode* connect(Node* root) {\n\tif(!root || !root->left) return root;                     // if given empty tree OR root is leaf node\n\troot->left->next = root->right;                           // making left child\'s next point to right child\n\tif(root->next) root->right->next = root->next->left;      // right child\'s next point to its parent\'s next\'s left node\n\troot->left = connect(root->left);                         // connect all next pointers in left subtree\n\troot->right = connect(root->right);                       // connect all next pointers in right subtree\n\treturn root;\n}\n```\n\nThanks! Upvote if this helped you!
['Depth-First Search', 'Recursion', 'C']