2 ms | Easy to Understand | Using Queue | Level Order Traversal | Java | C++
Intuition\n Describe your first thoughts on how to solve this problem. \nThe approach used here is based on level-order traversal of the tree using a queue. The
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe approach used here is based on level-order traversal of the tree using a queue. The intuition behind the solution is that by traversing the tree level by level, we can keep track of the next right node for each node in the current level and establish the connections.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nA while loop processes each level. Inside the loop, a for loop iterates through each node, connecting it to the next node in the same level if applicable. Nodes with children are added to the queue for the next level. The process continues until all nodes in the current level are processed.\n\n# Complexity\n- Time complexity: $$O(n)$$ \n    (n is number of nodes)\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $$O(m)$$ \n  (m is maximum number of nodes in a level)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```Java []\nclass Solution {\n    public Node connect(Node root) {\n        if (root == null) {\n            return null;\n        }\n\n        Queue<Node> queue = new LinkedList<>();\n        queue.add(root);\n\n        while (!queue.isEmpty()) {\n            int size = queue.size(); // Store the size of the current level\n\n            for (int i = 0; i < size; i++) {\n                Node node = queue.remove(); // Remove a node from the queue\n\n                if (i < size - 1) {\n                    node.next = queue.peek(); // Set the next pointer to the node at the front of the queue\n                }\n\n                if (node.left != null) {\n                    queue.add(node.left); // Add the left child to the queue\n                }\n                if (node.right != null) {\n                    queue.add(node.right); // Add the right child to the queue\n                }\n            }\n        }\n\n        return root; // Return the modified root node\n    }\n}\n\n```\n```C++ []\nclass Solution {\npublic:\n    Node* connect(Node* root) {\n        if (root == nullptr) return nullptr;\n\n        queue<Node*> queue;\n        queue.push(root);\n\n        while (!queue.empty()) {\n            int size = queue.size();\n\n            for (int i = 0; i < size; i++) {\n                Node* node = queue.front();\n                queue.pop();\n\n                if (i < size - 1) \n                    node->next = queue.front();\n                \n                if (node->left != nullptr) \n                    queue.push(node->left);\n                \n                if (node->right != nullptr) \n                    queue.push(node->right);              \n            }\n        }\n\n        return root;\n    }\n};\n\n```\nPLease upvote if u found it useful :)\n
['Breadth-First Search', 'Queue', 'Binary Tree', 'C++', 'Java']