DIY: Populating Next Right Pointers in Each Node II

Problem statement

You are given a binary tree that is not perfect. We have added an additional next pointer to our TreeNode implementation.

Populate each next pointer so it points 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.

Input

The input will be a perfect binary tree, and you will be provided with its root node. The following is an example input:

    3
   / \
  9  20
    /  \
   15   7

Output

The output will be the root node with every next pointer connected. For the above input, the output will be:

    3
   / \
  9  20
    /  \
   15   7

Coding exercise

For this coding exercise, you need to implement the traverse(root) function, where root is the root node of the binary tree. The function should return the same root node with every next pointer properly connected.