DIY: Populating Next Right Pointers in Each Node

Problem statement

You are given a perfect binary tree where all the leaves are on the same level and every parent has two children. 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
 / \   /  \
1   2 15   7

Output

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

     3 - null
   /   \
  9  -  20 - null
 / \   /  \
1 - 2-15 - 7 - null

Coding exercise

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