{"id":2906,"date":"2024-03-25T13:00:00","date_gmt":"2024-03-25T13:00:00","guid":{"rendered":"https:\/\/favtutor.com\/articles\/?p=2906"},"modified":"2024-03-27T05:51:48","modified_gmt":"2024-03-27T05:51:48","slug":"next-right-pointers-in-each-node","status":"publish","type":"post","link":"https:\/\/favtutor.com\/articles\/next-right-pointers-in-each-node\/","title":{"rendered":"Populating Next Right Pointers In Each Node (with code)"},"content":{"rendered":"\n

A perfect binary tree is where all leaves are on the same level with every parent having two children. In this article, we will discuss the leetcode problem where we will Populate Next Right Pointers In Each Node based on a perfectly balanced binary tree.<\/p>\n\n\n\n

Next Right Pointers In Each Node Problem<\/strong><\/h2>\n\n\n\n

In this problem, we are given a perfectly balanced binary tree where all the leaf nodes of the tree are at the same level. We have to place the right pointers as the next node in each node. If there is no right node present mark its next node as NULL.<\/p>\n\n\n\n

Let\u2019s examine this with an example:<\/p>\n\n\n\n

\"Example\"\/<\/figure>\n\n\n\n

In the above example, orange lines indicate the next pointer to each node.<\/p>\n\n\n\n

The basic approach to solving this question is to visit each node find its level and store that node in a map according to its level. After traversing the whole array we will traverse the map according to levels and keep marking the next node with the next value of that level. If it is the last node we will mark its next node NULL.<\/p>\n\n\n\n

Let\u2019s examine the approach step by step:<\/p>\n\n\n\n

    \n
  1. First, create a hash map that will store the nodes of the tree level-wise.<\/li>\n\n\n\n
  2. After that create a function that will take the current node and level as variables, now push the value of a node in the hash map according to its level.<\/li>\n\n\n\n
  3. After that call the function for the left and the right node by increasing the level by 1.<\/li>\n\n\n\n
  4. Once we have visited the whole tree, call the hash map and mark the next node with the next value of that level. If the next value is not present mark its next node NULL.<\/li>\n<\/ol>\n\n\n\n

    The time complexity for the above process is O(n) as we are visiting the tree once using DFS. DFS time complexity is O(n) so the overall time complexity is O(n). The space complexity will be O(n) as we are storing the values into the hash map whose time complexity is O(n).<\/p>\n\n\n\n

    Optimized Solution<\/strong><\/h2>\n\n\n\n

    In the above approach, we are storing the values into the hash map which is taking O(n) space complexity. To reduce this space complexity to constant space we will do level-wise traversal. Here’s how to do it:<\/p>\n\n\n\n

      \n
    1. First, create a queue that will store the nodes on a level.<\/li>\n\n\n\n
    2. Store the root node in the queue. After pushing the root node push NULL. NULL indicates that this level ends here. After that next level will start.<\/li>\n\n\n\n
    3. Now iterate the queue till its size becomes 0. <\/li>\n\n\n\n
    4. Now take out the current node from the queue and store it in a temp variable. Check if the next node present in the queue is NULL or not.<\/li>\n\n\n\n
    5. If it is not NULL mark the next of temp as this node If it is NULL mark the next of temp NULL and take out that node from the queue. Push the NULL node in the queue.<\/li>\n\n\n\n
    6. After that push the left and the right node in the queue.<\/li>\n<\/ol>\n\n\n\n

      Now, it’s time to implement it.<\/p>\n\n\n\n

      C++ Code<\/strong><\/h3>\n\n\n\n

      Below is the C++ implementation to populate the next right pointers in each node:<\/p>\n\n\n\n

      #include<bits\/stdc++.h>\n\nusing namespace std;\n\nclass Node{\n\n\u00a0\u00a0\u00a0\u00a0public:\n\n\u00a0\u00a0\u00a0\u00a0int val;\n\n\u00a0\u00a0\u00a0\u00a0Node* left;\n\n\u00a0\u00a0\u00a0\u00a0Node* right;\n\n\u00a0\u00a0\u00a0\u00a0Node* next;\n\n\u00a0\u00a0\u00a0\u00a0Node(int x){\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0val = x;\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0left = NULL;\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0right = NULL;\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0next = NULL;\n\n\u00a0\u00a0\u00a0\u00a0}\n\n};\n\nNode* find_next(Node* root){\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0if(root == NULL) return root;\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0queue<Node*>q;\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0q.push(root);\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0q.push(NULL);\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0while(q.size()){\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0Node* temp = q.front();\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0if(temp ==NULL){\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0q.pop();\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0if(q.size()) q.push(NULL);\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0continue;\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0}\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0q.pop();\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0if(q.front()){\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0temp->next = q.front();\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0}\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0if(temp->left) q.push(temp->left);\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0if(temp->right) q.push(temp->right);\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0}\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0return root;\n\n}\n\nint main(){\n\n\u00a0\u00a0\u00a0\u00a0Node* root =\u00a0 new Node(1);\n\n\u00a0\u00a0\u00a0\u00a0root->left = new Node(2);\n\n\u00a0\u00a0\u00a0\u00a0root->right = new Node(3);\n\n\u00a0\u00a0\u00a0\u00a0root->left->left = new Node(4);\n\n\u00a0\u00a0\u00a0\u00a0root->left->right = new Node(5);\n\n\u00a0\u00a0\u00a0\u00a0root->right->left = new Node(6);\n\n\u00a0\u00a0\u00a0\u00a0root->right->right = new Node(7);\n\n\u00a0\u00a0\u00a0\u00a0find_next(root);\n\n\u00a0\u00a0\u00a0\u00a0return 0;\n\n}<\/pre><\/div>\n\n\n\n
      Java Code<\/strong><\/h3>\n\n\n\n
      Below is the Java program for the solution:<\/p>\n\n\n\n
      import java.util.LinkedList;\n\nimport java.util.Queue;\n\nclass Node {\n\n\u00a0\u00a0\u00a0\u00a0int val;\n\n\u00a0\u00a0\u00a0\u00a0Node left, right, next;\n\n\u00a0\u00a0\u00a0\u00a0Node(int x) {\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0val = x;\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0left = null;\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0right = null;\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0next = null;\n\n\u00a0\u00a0\u00a0\u00a0}\n\n}\n\nclass NextPointer {\n\n\u00a0\u00a0\u00a0\u00a0static Node findNext(Node root) {\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0if (root == null) return root;\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0Queue<Node> q = new LinkedList<>();\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0q.add(root);\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0q.add(null);\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0while (!q.isEmpty()) {\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0Node temp = q.poll();\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0if (temp == null) {\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0if (!q.isEmpty()) q.add(null);\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0continue;\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0}\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0if (q.peek() != null) {\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0temp.next = q.peek();\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0}\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0if (temp.left != null) q.add(temp.left);\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0if (temp.right != null) q.add(temp.right);\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0}\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0return root;\n\n\u00a0\u00a0\u00a0\u00a0}\n\n\u00a0\u00a0\u00a0\u00a0public static void main(String[] args) {\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0Node root = new Node(1);\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0root.left = new Node(2);\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0root.right = new Node(3);\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0root.left.left = new Node(4);\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0root.left.right = new Node(5);\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0root.right.left = new Node(6);\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0root.right.right = new Node(7);\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0findNext(root);\n\n\u00a0\u00a0\u00a0\u00a0}\n\n}<\/pre><\/div>\n\n\n\n
      Python Code<\/strong><\/h3>\n\n\n\n
      We can implement it in Python also:<\/p>\n\n\n\n
      from queue import Queue\n\nclass Node:\n\n\u00a0\u00a0\u00a0\u00a0def __init__(self, x):\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0self.val = x\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0self.left = None\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0self.right = None\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0self.next = None\n\ndef find_next(root):\n\n\u00a0\u00a0\u00a0\u00a0if root is None:\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0return root\n\n\u00a0\u00a0\u00a0\u00a0q = Queue()\n\n\u00a0\u00a0\u00a0\u00a0q.put(root)\n\n\u00a0\u00a0\u00a0\u00a0q.put(None)\n\n\u00a0\u00a0\u00a0\u00a0while not q.empty():\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0temp = q.get()\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0if temp is None:\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0if not q.empty():\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0q.put(None)\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0continue\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0if not q.empty() and q.queue[0] is not None:\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0temp.next = q.queue[0]\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0if temp.left:\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0q.put(temp.left)\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0if temp.right:\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0q.put(temp.right)\n\n\u00a0\u00a0\u00a0\u00a0return root\n\nif __name__ == "__main__":\n\n\u00a0\u00a0\u00a0\u00a0root = Node(1)\n\n\u00a0\u00a0\u00a0\u00a0root.left = Node(2)\n\n\u00a0\u00a0\u00a0\u00a0root.right = Node(3)\n\n\u00a0\u00a0\u00a0\u00a0root.left.left = Node(4)\n\n\u00a0\u00a0\u00a0\u00a0root.left.right = Node(5)\n\n\u00a0\u00a0\u00a0\u00a0root.right.left = Node(6)\n\n\u00a0\u00a0\u00a0\u00a0root.right.right = Node(7)\n\n\u00a0\u00a0\u00a0\u00a0find_next(root)<\/pre><\/div>\n\n\n\n
      The time complexity to populate the next right pointers in each node is O(n). The space complexity is O(1) as we are not using any extra space. Here’s how both the approaches compare and reduce space complexity:<\/p>\n\n\n\n
      Approach<\/strong><\/th>Time Complexity<\/strong><\/th>Space Complexity<\/strong><\/th>Description<\/strong><\/th><\/tr><\/thead>
      Brute Force<\/td>O(n)<\/td>O(n)<\/td>We are storing the values into the hash map whose space complexity is O(n).<\/td><\/tr>
      Optimized <\/td>O(n)<\/td>O(1)<\/td>We are doing level-wise traversal which reduced our space complexity to O(1).<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n
      Conclusion<\/strong><\/h2>\n\n\n\n
      In this article, we discussed various methods to populate Next Right Pointers In Each Node problem from leetcode<\/a>. We had seen that by using hash-map we are taking extra O(n) space which can be reduced if we use level-wise traversal. Now, check how to print the right-side view of a binary tree<\/a>, which is also as interesting.<\/p>\n","protected":false},"excerpt":{"rendered":"
      Understand the problem “Next Right Pointers In Each Node” from leetcode with solution implementation in  C++, Java and Python.<\/p>\n","protected":false},"author":14,"featured_media":2910,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"jnews-multi-image_gallery":[],"jnews_single_post":null,"jnews_primary_category":{"id":"","hide":""},"footnotes":""},"categories":[7],"tags":[14,15],"class_list":["post-2906","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-data-structures-algorithms","tag-dsa","tag-leetcode"],"_links":{"self":[{"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/posts\/2906","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/users\/14"}],"replies":[{"embeddable":true,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/comments?post=2906"}],"version-history":[{"count":4,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/posts\/2906\/revisions"}],"predecessor-version":[{"id":2924,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/posts\/2906\/revisions\/2924"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/media\/2910"}],"wp:attachment":[{"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/media?parent=2906"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/categories?post=2906"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/tags?post=2906"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}