1 of 7

The problem of building a tree from a flat array has been solved here with this recursive solution:

/**
 * Build a tree from a flat array in PHP
 *
 * Authors: @DSkinner, @ImmortalFirefly and @SteveEdson
 *
 * @link http://stackoverflow.com/a/28429487/2078474
 */
function buildTree( array &$elements, $parentId = 0 )
{
    $branch = array();
    foreach ( $elements as &$element )
    {
        if ( $element['parent_id'] == $parentId )
        {
            $children = buildTree( $elements, $element['id'] );
            if ( $children )
            {
                $element['children'] = $children;
            }
            $branch[$element['id']] = $element;
            unset( $element );
        }
    }
    return $branch;
}

Now we only have to define a simple helper function:

/**
 * Transform a navigational menu to it's tree structure
 *
 * @uses  buildTree()
 * @uses  wp_get_nav_menu_items()
 *
 * @param  String     $menud_id 
 * @return Array|null $tree 
 */
function wpse_nav_menu_2_tree( $menu_id )
{
    $items = wp_get_nav_menu_items( $menu_id );

    if( ! $items )
        return;

    $tmp = [];
    foreach( $items as $key => $item )
        $tmp[$item->ID] = [ 
            'id'        => $item->ID, 
            'parent_id' => $item->menu_item_parent, 
            'title'     => $item->title 
        ];

    return buildTree( $tmp, 0 );
}

Now it becomes super easy to transform a navigational menu into it's tree structure with:

if( function_exists( 'wpse_nav_menu_2_tree' ) )
{
    $tree = wpse_nav_menu_2_tree( 'my_menu' );  // <-- Modify this to your needs!
    print_r( $tree );
}

For JSON, we can simply use:

$json = json_encode( $tree );