{"id":8924,"date":"2025-08-04T13:32:26","date_gmt":"2025-08-04T08:02:26","guid":{"rendered":"https:\/\/namastedev.com\/blog\/?p=8924"},"modified":"2025-08-04T15:20:43","modified_gmt":"2025-08-04T09:50:43","slug":"populating-next-right-pointers-in-each-node","status":"publish","type":"post","link":"https:\/\/namastedev.com\/blog\/populating-next-right-pointers-in-each-node\/","title":{"rendered":"Populating Next Right Pointers in Each Node"},"content":{"rendered":"\n<!-- SubTree Another: 21 -->\n<link\n    href=\"https:\/\/cdn.jsdelivr.net\/npm\/prismjs@1.29.0\/themes\/prism-tomorrow.min.css\"\n    rel=\"stylesheet\"\n\/>\n<script src=\"https:\/\/cdn.jsdelivr.net\/npm\/prismjs@1.29.0\/prism.min.js\"><\/script>\n<script src=\"https:\/\/cdn.jsdelivr.net\/npm\/prismjs@1.29.0\/plugins\/autoloader\/prism-autoloader.min.js\"><\/script>\n\n<style> \n.wp_blog_theme {\n  --primary: #E58C32;\n  --secondary: #f8c291;\n  --light-bg: #fef9f4;\n  --text-dark: #2d2d2d;\n  --tab-radius: 12px;\n  --shadow: 0 4px 12px rgba(0, 0, 0, 0.08);\n  --code-bg: #001f3f;\n  --code-text: #d4f1ff;\n}\n\n.wp_blog_container {\n  font-family: 'Segoe UI', sans-serif;\n  background: var(--light-bg);\n  margin: 0;\n  padding: 0;\n  color: var(--text-dark);\n}\n\n\/* Heading *\/\n.wp_blog_main-heading {\n  text-align: center;\n  font-size: 2.4rem;\n  color: var(--primary);\n  margin-top: 2.5rem;\n  font-weight: bold;\n}\n\n\/* Explanation Card *\/\n.wp_blog_explanation,\n.wp_blog_code-tabs-container {\n  max-width: 940px;\n  margin: 2rem auto;\n  padding: 2rem;\n  background: white;\n  border-radius: var(--tab-radius);\n  box-shadow: var(--shadow);\n}\n\n\/* Text and Visuals *\/\n.wp_blog_explanation h2{\n  font-size: 1.4rem;\n  color: var(--primary);\n  margin-bottom: 0.5rem;\n}\n.wp_blog_explanation h5{\n  color: var(--primary);\n}\n\n.wp_blog_explanation p,\n.wp_blog_explanation li {\n  font-size: 1.05rem;\n  line-height: 1.7;\n  margin: 0.5rem 0;\n}\n.wp_blog_explanation code {\n  background: #f9cea6;\n  color: #2d2d2d;\n  padding: 3px 6px;\n  border-radius: 4px;\n  font-family: 'Courier New', monospace;\n}\n.wp_blog_explanation img {\n  max-width: 100%;\n  border-radius: var(--tab-radius);\n  margin-top: 1rem;\n  box-shadow: 0 2px 12px rgba(0,0,0,0.06);\n}\n\n\/* Tab Buttons *\/\n.wp_blog_code-tabs-header {\n  display: flex;\n  flex-wrap: wrap;\n  gap: 0.5rem;\n  margin-bottom: 1rem;\n}\n.wp_blog_code-tab-button {\n  padding: 0.6rem 1.2rem;\n  border: 1px solid var(--primary);\n  background: white;\n  color: var(--primary);\n  border-radius: 50px;\n  font-weight: 600;\n  cursor: pointer;\n  transition: all 0.3s ease;\n}\n.wp_blog_code-tab-button:hover {\n  background: var(--secondary);\n}\n.wp_blog_code-tab-button.active {\n  background: var(--primary);\n  color: white;\n}\n\n\/* Code Content *\/\n.wp_blog_code-tab-content {\n  display: none;\n  background: var(--code-bg);\n  border-radius: var(--tab-radius);\n}\n.wp_blog_code-tab-content.active {\n  display: block;\n}\n.wp_blog_code-tab-content pre {\n  margin: 0;\n  padding: 1.5rem;\n  font-size: 1rem;\n  overflow-x: auto;\n  background: var(--code-bg);\n  border-radius: var(--tab-radius);\n  color: var(--code-text);\n}\n<\/style>\n\n<div class=\"wp_blog_container wp_blog_theme\"> \n    <h1 class=\"wp_blog_main-heading\"><\/h1>\n    <div class=\"wp_blog_explanation\">\n        <h2>Problem Statement:<\/h2>\n        <p>You are given a <strong>perfect binary tree<\/strong> where all leaves are on the same level, and every parent has two children. The binary tree has the following definition:<\/p>\n        <pre>\n            struct Node {\n                int val;\n                Node *left;\n                Node *right;\n                Node *next;\n                }\n        <\/pre>\n\n        <p>Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to <code>NULL<\/code>.<\/p>\n        \n        <p>Initially, all next pointers are set to <code>NULL<\/code>.<\/p>\n        <h2>Examples:<\/h2>\n                <h3>Example 1:<\/h3>\n                <img decoding=\"async\" src=\"https:\/\/namastedev.com\/blog\/wp-content\/uploads\/2025\/08\/Screenshot-2025-08-04-at-12.16.08\u202fPM.png\" alt=\"\">\n                <p><strong>Input:<\/strong> root = [1,2,3,4,5,6,7]<\/p>\n                <p><strong>Output:<\/strong> [1,#,2,3,#,4,5,6,7,#]<\/p>\n                <p><strong>Explanation:<\/strong> Given the above perfect binary tree (Figure A), your function should populate each next pointer to point to its next right node, just like in Figure B. The serialized output is in level order as connected by the next pointers, with &#8216;#&#8217; signifying the end of each level.<\/p>\n                \n                <h3>Example 2:<\/h3>\n                <p><strong>Input:<\/strong> root = []<\/p>\n                <p><strong>Output:<\/strong> []<\/p>\n\n                    <h2>Constraints:<\/h2>\n                    <ul>\n                        <li>The number of nodes in the tree is in the range <code>[0, 2<sup>12<\/sup> - 1]<\/code>.<\/li>\n                        <li><code>-1000 <= Node.val <= 1000<\/code><\/li>\n                    <\/ul>\n\n                <h2>Approach<\/h2>\n                <ul>\n                    <li>Use DFS (Depth-First Search) to connect nodes.<\/li>\n                    <li>For each node: \n                        <ul>\n                            <li>Set <code>left.next = right<\/code>.<\/li>\n                            <li>If <code>next<\/code> exists, connect <code>right.next = next.left<\/code>.<\/li>\n                        <\/ul>\n                    <\/li>\n                    <li>Recursively repeat for left and right children.<\/li>\n                <\/ul>\n\n                <h2>Time Complexity:<\/h2>\n                <li>\n                  <p><strong>Time Complexity = O(n * m)<\/strong>\n                  <\/li>\n                <h2>Space Complexity:<\/h2>\n                <li>\n                  <p><strong>Space Complexity = O(log n)<\/strong> recursion stack space (h=tree height)<\/p>\n                <\/li>\n<h2>Dry Run<\/h2>\n<div style=\"background: #f9f9f9; padding: 10px; border: 1px solid #ccc; font-family: monospace;\">\n<b>Function Call:<\/b> connect(root) where<br>\nroot = Node(1)<br>\n\u251c\u2500\u2500 left: Node(2)<br>\n\u2502\u00a0\u00a0 \u251c\u2500\u2500 left: Node(4)<br>\n\u2502\u00a0\u00a0 \u2514\u2500\u2500 right: Node(5)<br>\n\u2514\u2500\u2500 right: Node(3)<br>\n&nbsp;&nbsp;&nbsp;&nbsp;\u251c\u2500\u2500 left: Node(6)<br>\n&nbsp;&nbsp;&nbsp;&nbsp;\u2514\u2500\u2500 right: Node(7)<br><br>\n\n<b>Step 1:<\/b><br>\n\u2192 Call traversal(curr = root = 1)<br><br>\n\n\u2192 curr.left = 2 \u2192 set 2.next = 3<br>\n\u2192 curr.right = 3 and curr.next = null \u2192 skip setting 3.next<br>\n\u2192 Call traversal(curr = 2)<br><br>\n\n\u2192 curr.left = 4 \u2192 set 4.next = 5<br>\n\u2192 curr.right = 5 and curr.next = 3 \u2192 set 5.next = 3.left = 6<br>\n\u2192 Call traversal(curr = 4)<br>\n\n\u2192 curr.left = null \u2192 skip<br>\n\u2192 curr.right = null \u2192 skip<br>\n\u2192 Return<br><br>\n\n\u2192 Call traversal(curr = 5)<br>\n\n\u2192 curr.left = null \u2192 skip<br>\n\u2192 curr.right = null \u2192 skip<br>\n\u2192 Return<br><br>\n\n\u2192 Return from traversal(curr = 2)<br><br>\n\n\u2192 Call traversal(curr = 3)<br>\n\n\u2192 curr.left = 6 \u2192 set 6.next = 7<br>\n\u2192 curr.right = 7 and curr.next = null \u2192 skip setting 7.next<br>\n\u2192 Call traversal(curr = 6)<br>\n\n\u2192 curr.left = null \u2192 skip<br>\n\u2192 curr.right = null \u2192 skip<br>\n\u2192 Return<br><br>\n\n\u2192 Call traversal(curr = 7)<br>\n\n\u2192 curr.left = null \u2192 skip<br>\n\u2192 curr.right = null \u2192 skip<br>\n\u2192 Return<br><br>\n\n\u2192 Return from traversal(curr = 3)<br><br>\n\n<b>Final Result:<\/b> The tree is modified such that each node's next pointer points to its adjacent node on the same level.\n<\/div>\n\n\n\n    <!-- <h2>Visualisation:<\/h2>\n        <img decoding=\"async\" src=\"https:\/\/namastedev.com\/blog\/wp-content\/uploads\/2025\/07\/Screenshot-2025-07-19-at-5.23.43\u202fPM.png\" alt=\"longest\" \/> -->\n    <\/div>\n    \n\n    <div class=\"wp_blog_code-tabs-container\">\n        <div class=\"wp_blog_code-tabs-header\">\n            <button class=\"wp_blog_code-tab-button active\" data-lang=\"js\">JavaScript<\/button>\n            <button class=\"wp_blog_code-tab-button\" data-lang=\"py\">Python<\/button>\n            <button class=\"wp_blog_code-tab-button\" data-lang=\"java\">Java<\/button>\n            <button class=\"wp_blog_code-tab-button\" data-lang=\"cpp\">C++<\/button>\n            <button class=\"wp_blog_code-tab-button\" data-lang=\"c\">C<\/button>\n            <button class=\"wp_blog_code-tab-button\" data-lang=\"cs\">C#<\/button>\n        <\/div>\n\n        <!-- JavaScript -->\n        <div class=\"wp_blog_code-tab-content active\" data-lang=\"js\">\n            <pre><code class=\"language-javascript\">\nvar connect = function(root) {\n    if(!root) return root;\n    let traversal = (curr) => {\n        if(curr.left) {\n            curr.left.next = curr.right;\n        }\n        if(curr.right && curr.next) {\n            curr.right.next = curr.next.left;\n        }\n        curr.left && traversal(curr.left);\n        curr.right && traversal(curr.right);\n    }\n    traversal(root);\n    return root;\n};\n  <\/code><\/pre>\n        <\/div>\n\n        <!-- Python -->\n        <div class=\"wp_blog_code-tab-content\" data-lang=\"py\">\n            <pre><code class=\"language-python\">\nclass Node:\n    def __init__(self, val=0, left=None, right=None, next=None):\n        self.val = val\n        self.left = left\n        self.right = right\n        self.next = next\ndef connect(root):\n    if not root:\n        return root\n    def traversal(curr):\n        if curr.left:\n            curr.left.next = curr.right\n        if curr.right and curr.next:\n            curr.right.next = curr.next.left\n        if curr.left:\n            traversal(curr.left)\n        if curr.right:\n            traversal(curr.right)\n    traversal(root)\n    return root\n            <\/code><\/pre>\n        <\/div>\n\n        <!-- Java -->\n        <div class=\"wp_blog_code-tab-content\" data-lang=\"java\">\n            <pre><code class=\"language-java\">\nclass Node {\n    public int val;\n    public Node left;\n    public Node right;\n    public Node next;\n    public Node(int val) {\n        this.val = val;\n    }\n}\nclass Solution {\n    public Node connect(Node root) {\n        if (root == null) return null;\n\n        traverse(root);\n        return root;\n    }\n    private void traverse(Node curr) {\n        if (curr.left != null) {\n            curr.left.next = curr.right;\n        }\n        if (curr.right != null && curr.next != null) {\n            curr.right.next = curr.next.left;\n        }\n        if (curr.left != null) traverse(curr.left);\n        if (curr.right != null) traverse(curr.right);\n    }\n}\n     <\/code><\/pre>\n        <\/div>\n\n        <!-- C++ -->\n        <div class=\"wp_blog_code-tab-content\" data-lang=\"cpp\">\n            <pre><code class=\"language-cpp\">\nclass Node {\npublic:\n    int val;\n    Node* left;\n    Node* right;\n    Node* next;\n    Node(int _val) : val(_val), left(nullptr), right(nullptr), next(nullptr) {}\n};\nclass Solution {\npublic:\n    Node* connect(Node* root) {\n        if (!root) return root;\n        auto traversal = [&](Node* curr, auto&& traversal_ref) -> void {\n            if (curr->left) {\n                curr->left->next = curr->right;\n            }\n            if (curr->right && curr->next) {\n                curr->right->next = curr->next->left;\n            }\n            if (curr->left) traversal_ref(curr->left, traversal_ref);\n            if (curr->right) traversal_ref(curr->right, traversal_ref);\n        };\n        traversal(root, traversal);\n        return root;\n    }\n};\n    <\/code><\/pre>\n        <\/div>\n\n        <!-- C -->\n        <div class=\"wp_blog_code-tab-content\" data-lang=\"c\">\n            <pre><code class=\"language-c\">\ntypedef struct Node {\n    int val;\n    struct Node* left;\n    struct Node* right;\n    struct Node* next;\n} Node;\nvoid traversal(Node* curr) {\n    if (!curr) return;\n    \n    if (curr->left) {\n        curr->left->next = curr->right;\n    }\n    if (curr->right && curr->next) {\n        curr->right->next = curr->next->left;\n    }\n\n    if (curr->left) traversal(curr->left);\n    if (curr->right) traversal(curr->right);\n}\nNode* connect(Node* root) {\n    if (!root) return NULL;\n    traversal(root);\n    return root;\n}\n            <\/code><\/pre>\n        <\/div>\n\n        <!-- C# -->\n        <div class=\"wp_blog_code-tab-content\" data-lang=\"cs\">\n            <pre><code class=\"language-csharp\">\npublic class Node {\n    public int val;\n    public Node left;\n    public Node right;\n    public Node next;\n    public Node(int val = 0, Node left = null, Node right = null, Node next = null) {\n        this.val = val;\n        this.left = left;\n        this.right = right;\n        this.next = next;\n    }\n}\npublic class Solution {\n    public Node Connect(Node root) {\n        if (root == null) return root;\n        void Traverse(Node curr) {\n            if (curr.left != null) {\n                curr.left.next = curr.right;\n            }\n            if (curr.right != null && curr.next != null) {\n                curr.right.next = curr.next.left;\n            }\n            if (curr.left != null) Traverse(curr.left);\n            if (curr.right != null) Traverse(curr.right);\n        }\n        Traverse(root);\n        return root;\n    }\n}\n            <\/code><\/pre>\n        <\/div>\n    <\/div>\n<\/div>\n\n<script>\n    document.addEventListener(\"DOMContentLoaded\", () => {\n        const buttons = document.querySelectorAll(\".wp_blog_code-tab-button\");\n        const contents = document.querySelectorAll(\".wp_blog_code-tab-content\");\n\n        buttons.forEach((button) => {\n            button.addEventListener(\"click\", () => {\n                const lang = button.getAttribute(\"data-lang\");\n\n                buttons.forEach((btn) => btn.classList.remove(\"active\"));\n                contents.forEach((content) =>\n                    content.classList.remove(\"active\")\n                );\n\n                button.classList.add(\"active\");\n                document\n                    .querySelector(`.wp_blog_code-tab-content[data-lang=\"${lang}\"]`)\n                    .classList.add(\"active\");\n            });\n        });\n    });\n<\/script>\n","protected":false},"excerpt":{"rendered":"<p>Problem Statement: You are given a perfect binary tree where all leaves are on the same level, and every parent has two children. The binary tree has the following definition: struct Node { int val; Node *left; Node *right; Node *next; } Populate each next pointer to point to its next right node. If there<\/p>\n","protected":false},"author":108,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"om_disable_all_campaigns":false,"_monsterinsights_skip_tracking":false,"_monsterinsights_sitenote_active":false,"_monsterinsights_sitenote_note":"","_monsterinsights_sitenote_category":0,"footnotes":""},"categories":[322,176,175,211,811,174,172,173],"tags":[],"class_list":{"0":"post-8924","1":"post","2":"type-post","3":"status-publish","4":"format-standard","6":"category-algorithms-and-data-structures","7":"category-csharp","8":"category-cplusplus","9":"category-data-structures","10":"category-data-structures-and-algorithms","11":"category-java","12":"category-javascript","13":"category-python"},"aioseo_notices":[],"_links":{"self":[{"href":"https:\/\/namastedev.com\/blog\/wp-json\/wp\/v2\/posts\/8924","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/namastedev.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/namastedev.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/namastedev.com\/blog\/wp-json\/wp\/v2\/users\/108"}],"replies":[{"embeddable":true,"href":"https:\/\/namastedev.com\/blog\/wp-json\/wp\/v2\/comments?post=8924"}],"version-history":[{"count":1,"href":"https:\/\/namastedev.com\/blog\/wp-json\/wp\/v2\/posts\/8924\/revisions"}],"predecessor-version":[{"id":8926,"href":"https:\/\/namastedev.com\/blog\/wp-json\/wp\/v2\/posts\/8924\/revisions\/8926"}],"wp:attachment":[{"href":"https:\/\/namastedev.com\/blog\/wp-json\/wp\/v2\/media?parent=8924"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/namastedev.com\/blog\/wp-json\/wp\/v2\/categories?post=8924"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/namastedev.com\/blog\/wp-json\/wp\/v2\/tags?post=8924"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}