DIY: Binary Tree Level Order Traversal

Problem statement

Given a binary tree, populate an array to represent its level-by-level traversal. You should populate the values of each levels’ nodes from left to right in separate sublists.

Input

The input will be a 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 a list of lists in which each nested list will represent the elements of a single level. For the above input, the output will be:

[
  [3],
  [9,20],
  [15,7]
]

Coding exercise

For this coding exercise, you need to implement the function traverse(root), where root is the root node of the binary tree. The function should return the level-by-level values of the binary tree in separate sub-lists.