✅ [C++/Python/Java] Simple Solution w/ Images & Explanation | BFS + DFS + O(1) Optimized BFS
We are given a perfect binary tree and we need to populate next pointers in each node of the tree\n\n---\n\n\u2714\uFE0F Solution - I (BFS - Right to Left)\n\nI
We are given a perfect binary tree and we need to populate next pointers in each node of the tree\n\n---\n\n\u2714\uFE0F ***Solution - I (BFS - Right to Left)***\n\nIt\'s important to see that the given tree is a **perfect binary tree**. This means that each node will always have both children and only the last level of nodes will have no children.\n\n<p align=middle><img src=https://assets.leetcode.com/uploads/2019/02/14/116_sample.png width=500 />\n\nNow, we need to populate next pointers of each node with nodes that occur to its immediate right on the same level. This can easily be done with BFS. Since for each node, we require the right node on the same level, we will perform a **right-to-left BFS** instead of the standard left-to-right BFS.\n\nBefore starting the traversal of each level, we would initialize a `rightNode` variable set to NULL. Then, since we are performing right-to-left BFS, we would be starting at rightmost node of each level. We set the next node of `cur` as `rightNode` and update `rightNode = cur`. This would ensure that each node would be assigned its `rightNode` properly while traversing from right to left. \nAlso, if `cur` has a child, we would first push its right child and only then its left child (since we are doing right-to-left BFS). Once BFS is completed (after queue becomes empty), all next node would be populated and we can finally return `root`.\n\nThe process is illustrated below -\n\n<table>\n<tr>\n<td colspan=4>\n<p align=middle>\n<img src=https://assets.leetcode.com/users/images/01e68f51-4905-4f58-b2dd-061aa64c8a91_1640764834.4913242.png width=350   />\n</p>\n</td>\n</tr>\n\n<tr></tr>\n\n<tr>\n<td colspan=4>\n<p align=middle>\n<img src=https://assets.leetcode.com/users/images/e2a49b2c-1493-4e3f-bb36-28b89153bf73_1640768916.6068268.png  width=350  />\n<img src=https://assets.leetcode.com/users/images/67ff2271-2b5d-4b5f-8e31-6e14809146ad_1640765277.2783518.png  width=350   />\n</p>\n</td>\n\n</tr>\n\n<tr></tr>\n\n<tr>\n<td colspan=4>\n<p align=middle>\n<img src=https://assets.leetcode.com/users/images/e1067d5d-3c94-4efc-b202-f4d18b93a0ac_1640765388.5706594.png  width=350  />\n<img src=https://assets.leetcode.com/users/images/d8a07cf0-aa8c-44b9-ab35-98a2e1422d43_1640765420.4366648.png  width=350  />\n<img src=https://assets.leetcode.com/users/images/ce1046fb-3212-46a5-b2f7-445ab32df816_1640765451.180103.png  width=350  />\n<img src=https://assets.leetcode.com/users/images/bd5a4aff-19fe-4aad-b4e6-5dee5156536f_1640765483.7865818.png  width=350  />\n</p>\n\n</tr>\n\n</table>\n\n\n\n\n\n\n\n**C++**\n```cpp\nclass Solution {\npublic:\n    Node* connect(Node* root) {\n        if(!root) return nullptr;\n        queue<Node*> q;\n        q.push(root);        \n        while(size(q)) {\n            Node* rightNode = nullptr;                    // set rightNode to null initially\n            for(int i = size(q); i; i--) {                // traversing each level\n                auto cur = q.front(); q.pop();            // pop a node from current level and,\n                cur -> next = rightNode;                  // set its next pointer to rightNode\n                rightNode = cur;                          // update rightNode as cur for next iteration\n                if(cur -> right)                          // if a child exists\n                    q.push(cur -> right),                 // IMP: push right first to do right-to-left BFS\n                    q.push(cur -> left);                  // then push left\n            }\n        }\n        return root;\n    }\n};\n```\n\n**Python**\n```python\nclass Solution:\n    def connect(self, root):\n        if not root: return None\n        q = deque([root])\n        while q:\n            rightNode = None\n            for _ in range(len(q)):\n                cur = q.popleft()\n                cur.next, rightNode = rightNode, cur\n                if cur.right:\n                    q.extend([cur.right, cur.left])\n        return root\n```\n\n**Java**\n```java\nclass Solution {\n    public Node connect(Node root) {\n        if(root == null) return null;\n        Queue<Node> q = new LinkedList<>();\n        q.offer(root);\n        while(!q.isEmpty()) {\n            Node rightNode = null;\n            for(int i = q.size(); i > 0; i--) {\n                Node cur = q.poll();\n                cur.next = rightNode;\n                rightNode = cur;\n                if(cur.right != null) {\n                    q.offer(cur.right);\n                    q.offer(cur.left);\n                }\n            }\n        }\n        return root;        \n    }\n}\n```\n\n***Time Complexity :*** `O(N)`, where `N` is the number of nodes in the given tree. We only traverse the tree once using BFS which  requires `O(N)`.\n***Space Complexity :*** `O(W) = O(N)`, where `W` is the width of given tree. This is required to store the nodes in queue. Since the given tree is a perfect binary tree, its width is given as `W = (N+1)/2 \u2248 O(N)`\n\n\n---\n\n\u2714\uFE0F ***Solution - II (DFS)***\n\nWe can also populate the next pointers recursively using DFS. This is slightly different logic than above but relies on the fact that the given tree is a perfect binary tree.\n\nIn the above solution, we had access to right nodes since we traversed in level-order. But in DFS, once we go to the next level, we cant get access to right node. So, we must update next pointers of the child of each node from the its parent\'s level itself. Thus at each recursive call -\n* If child node exists:\n\t* assign next of left child node as right child node: `root -> left -> next = root -> right`. Note that, if once child exists, the other exists as well.\n\t* assign next of right child node as left child of root\'s next (if root\'s next exists): `root -> right -> next = root -> next -> left`. \n\t**How?** We need right immediate node of right child. This wont exist if current root\'s next node doesnt exists. If next node of current root is present (the next pointer of root would already be populated in above level) , the right immediate node of root\'s right child must be root\'s next\'s left child because if child of root exists, then the child of root\'s next must also exist.\n\n* If child node doesn\'t exist, we have reached the last level, we can directly return since there\'s no child nodes to populate their next pointers\n\nThe process is very similar to the one illustrated in the image below with just the difference that we are traversing with DFS instead of BFS shown below.\n\n```cpp\nclass Solution {\npublic:\n    Node* connect(Node* root) {\n        if(!root) return nullptr;\n        auto L = root -> left, R = root -> right, N = root -> next;\n        if(L) {\n            L -> next = R;                                // next of root\'s left is assigned as root\'s right\n            if(N) R -> next = N -> left;                  // next of root\'s right is assigned as root\'s next\'s left (if root\'s next exist)\n            connect(L);                                   // recurse left  - simple DFS \n            connect(R);                                   // recurse right\n        }\n        return root;\n    }\n};\n```\n\n**Python**\n```python\nclass Solution:\n    def connect(self, root):\n        if not root: return None\n        L, R, N = root.left, root.right, root.next\n        if L:\n            L.next = R\n            if N: R.next = N.left\n            self.connect(L)\n            self.connect(R)\n        return root\n```\n\n**Java**\n```java\nclass Solution {\n    public Node connect(Node root) {\n        if(root == null) return null;\n        Node L = root.left, R = root.right, N = root.next;\n        if(L != null) {\n            L.next = R;\n            if(N != null) R.next = N.left;\n            connect(L);\n            connect(R);\n        }\n        return root;\n    }\n}\n```\n\n***Time Complexity :*** `O(N)`, each node is only traversed once\n***Space Complexity :*** `O(logN)`, required for recursive stack. The maximum depth of recursion is equal to the height of tree which in this case of perfect binary tree is equal to `O(logN)`\n\n---\n\n\u2714\uFE0F ***Solution - III (BFS - Space-Optimized Appraoch)***\n\nThis is a combination of logic of above logics- we will traverse in BFS manner but populate the next pointers of bottom level just as we did in the DFS solution.\n\nUsually standard DFS/BFS takes `O(N)` space, but since we are given the next pointers in each node, we can use them to space-optimize our traversal to `O(1)`. \n* We first populate the next pointers of child nodes of current level. This makes it possible to traverse the next level without using a queue. To populate next pointers of child, the exact same logic as above is used\n* We simply traverse to root\'s left child and repeat the process - traverse current level, fill next pointers of child nodes and then again update `root = root -> left`. So, we are basically performing standard BFS traversal in `O(1)` space by using next pointers to our advantage\n* The process continues till we reach the last level of tree\n\n\nThe process is illustrated in images below -\n\n\n<table>\n  <tr>\n    <th>Image</th>\n    <th>Description</th>\n  </tr>\n  \n  <tr>\n    <td><img src=https://assets.leetcode.com/users/images/b681da39-4c99-4e52-8cb8-779583022898_1640761933.124148.png  width=500 /></td>\n    <td>We start with a perfect binary tree with all next pointers initially NULL</td>\n  </tr>\n  \n  <tr></tr>\n  \n  <tr>\n    <td>\n<img src=https://assets.leetcode.com/users/images/ebbbfada-bd94-4432-ac4b-e0326fc34fd4_1640761979.3636644.png  width=500 /></td>\n    <td>We start traversal level-by-level, from left to right on each level</br>\n\t\n```cpp\ncur = root\n```\t\n\nEvery iteration, the next pointers of a node\'s child will be updated</br> \n\n```cpp\nif(cur -> left) {\n\tcur -> left -> next = cur -> right;\n\tif(cur -> next) cur -> right -> next = cur -> next -> left;\n}\n```\n\n</td>\n\n  </tr>\n  \n  <tr></tr>\n  \n  <tr>\n    <td><img src=https://assets.leetcode.com/users/images/4935430e-af1b-4fe1-9fc7-c5d35be45b90_1640761999.0506494.png  width=500 /></td>\n    <td>Move to next level</br>\n\n```cpp\nroot = root -> left\n// next iteration\ncur = root\n```\n\n& repeat:</br>\n\t\n```cpp\nif(cur -> left) {\n\tcur -> left -> next = cur -> right;\n\tif(cur -> next) cur -> right -> next = cur -> next -> left;\n}\n```\n\t\n</td>\n  </tr>\n  \n  <tr></tr>\n  \n  <tr>\n    <td><img src=https://assets.leetcode.com/users/images/9ada5f9e-34f7-4c0b-b513-2bd6ff758cbc_1640762014.5024235.png  width=500 /></td>\n    <td>Continue the same process with all nodes on current level</br>\n\t\n```cpp\nfor(; cur; cur = cur -> next)\n    // ...\n```\n\t\n</td>\n  </tr>\n  \n  <tr></tr>\n  \n  <tr>\n    <td><img src=https://assets.leetcode.com/users/images/8656dc5e-93fb-4260-87a7-a2261171b70d_1640762030.292751.png  width=500 /></td>\n    <td>No child node exists</br>\n\n```cpp\nif(cur -> left)\n    // ...\nelse break\n```\n\nSo, we break here. On the next iteration, root becomes NULL as well and we stop the process.\n</td>\n  </tr>\n</table>\n\n\n\n**C++**\n```cpp\nclass Solution {\npublic:\n    Node* connect(Node* root) {\n        auto head = root;\n        for(; root; root = root -> left) \n            for(auto cur = root; cur; cur = cur -> next)   // traverse each level - it\'s just BFS taking advantage of next pointers          \n                if(cur -> left) {                          // update next pointers of children if they exist               \n                    cur -> left -> next = cur -> right;\n                    if(cur -> next) cur -> right -> next = cur -> next -> left;\n                }\n                else break;                                // if no children exist, stop iteration                                                  \n        \n        return head;\n    }\n};\n```\n\n**Python**\n```python\nclass Solution:\n    def connect(self, root):\n        head = root\n        while root:\n            cur, root = root, root.left\n            while cur:\n                if cur.left:\n                    cur.left.next = cur.right\n                    if cur.next: cur.right.next = cur.next.left\n                else: break\n                cur = cur.next\n                \n        return head\n```\n\n**Java**\n```java\nclass Solution {\n    public Node connect(Node root) {\n        Node head = root;\n        for(; root != null; root = root.left) \n            for(Node cur = root; cur != null; cur = cur.next) \n                if(cur.left != null) {\n                    cur.left.next = cur.right;\n                    if(cur.next != null) cur.right.next = cur.next.left;\n                } else break;\n        \n        return head;\n    }\n}\n```\n\n***Time Complexity :*** `O(N)`, we only traverse each node once, basically doing a standard BFS.\n***Space Complexity :*** `O(1)`, only constant extra space is being used\n\n\n---\n---\n\n\uD83D\uDCBBIf there are any suggestions / questions / mistakes in my post, please do comment below \uD83D\uDC47 \n\n---\n---
[]