Populating Next Right Pointers in Each Node

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:
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 NULL.
Initially, all next pointers are set to NULL.

Example 1:

Input: root = {1,2,3,4,5,6,7}
Output: [1,#,2,3,#,4,5,6,7,#]

Approach

Java

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class PopulatingNextRightPointers {
    public static void main(String[] args) {
        Node root = new Node(1);
        root.left = new Node(2);
        root.right = new Node(3);
        root.left.left = new Node(4);
        root.left.right = new Node(5);
        root.right.right = new Node(7);
        Node root1 = connect(root);
        printTree(root1);
    }

    // function to connect nodes at the
    // each level
    static Node connect(Node root) {
        // if empty tree
        if (root == null)
            return null;

        // at level 0
        root.next = null;

        // call dfs
        dfs(root);
        return root;
    }

    // dfs function
    static void dfs(Node root) {

        // if tree is empty
        if (root == null)
            return;

        // if left is not null then point
        // left next to right
        if (root.left != null)
            root.left.next = root.right;

        // if right is not null then point right next as
        // if root next posible the root next left else
        // null
        if (root.right != null)
            root.right.next = root.next != null ? root.next.left : null;

        // call for left subtree
        dfs(root.left);

        // call for right subtree
        dfs(root.right);
    }

//function to print the tree
    static void printTree(Node root) {
        Queue<Node> q = new LinkedList<>();
        q.add(root);
        List<String> vec = new ArrayList<String>();
        while (!q.isEmpty()) {
            int len = q.size();
            while (len > 0) {
                len--;
                root = q.poll();
                if (root != null) {
                    vec.add(String.valueOf(root.val));
                    q.add(root.left);
                    q.add(root.right);
                }
            }
            vec.add("#");
        }
        for (int i = 0; i < vec.size() - 2; i++)
            System.out.print(vec.get(i) + ",");
        System.out.println(vec.get(vec.size() - 2));
    }

    static class Node {
        int val;
        Node left;
        Node right;
        Node next;

        Node(int val) {
            this.val = val;
            this.next = null;
            this.right = null;
            this.left = null;
        }

    }
}

C++

#include <bits/stdc++.h>
using namespace std;

struct Node {
  int val;
  Node *left;
  Node *right;
  Node *next;
  Node(int val) 
     {
      this->val=val;
      this->next=NULL;
      this->right=NULL;
      this->left=NULL;
      }

};

//dfs function 
void dfs(Node *root)
{

    //if tree is empty
    if(root==NULL)
              return;

    //if left is not null then point 
    //left next to right
    if(root->left)
        root->left->next=root->right;

    //if right is not null then point right next as 
    //if root next posible the root next left else
    //null
    if(root->right)
         root->right->next=root->next?root->next->left:NULL;
        
    //call for left subtree
    dfs(root->left);

    //call for right subtree
    dfs(root->right);
}
Node* connect(Node* root) 
{
   //if empty tree
    if(root==NULL)
           return NULL;
    
    //at level 0
    root->next=NULL;

    //call dfs 
    dfs(root);
    return root;
}

//function to print the tree
void printTree(Node *root)
{
    queue<Node*>q;
    q.push(root);
    vector<string> vec;
    while(!q.empty())
     {
         int len=q.size();
         while(len--)
         {  
           root=q.front();
           q.pop();
        
           
        if(root!=NULL)
          {
               vec.push_back(to_string(root->val));
              q.push(root->left);
              q.push(root->right);
          }
         }
         vec.push_back("#");
     }
      for(int i=0;i<vec.size()-2;i++)
        cout<<vec[i]<<",";
     cout<<vec[vec.size()-2];
}
int main()
{
  Node *root=new Node(1);
  root->left=new Node(2);
  root->right=new Node(3);
  root->left->left=new Node(4);
  root->left->right=new Node(5);
  root->right->left=new Node(6);
  root->right->right=new Node(7);
  Node *root1=connect(root);
  printTree(root1);
  return 0;
}