Convert output of nav_menu items into a tree-like multidimensional array

Is there any way to grab the nav menu items as a multidimensional array instead of a flat array?

By a tree-like structure I mean something that would preserve relationship between child and parent items, like so (this is just an example)…

array(
  array(
    'post_type' => 'page',
    'post_name' => 'Home',
    'children' => array() 
  ),
  array(
    'post_type' => 'page',
    'post_name' => 'About Us',
    'children' => array(
      array(
        'post_type' => 'page',
        'post_name' => 'Our History',
        'children' => array() 
      )
    ) 
  )
)

There is a wp_get_nav_menu_items() function but it returns a 1-dimensional array with all the items on the same level, which is not what I want. Does WordPress include a built-in way to get a multidimensional array for my menu items? If not, what is the best way to get wp_get_nav_menu_items() as a tree-like structure into a multidimensional array in terms of performance?

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

/**
 * Modification of "Build a tree from a flat array in PHP"
 *
 * Authors: @DSkinner, @ImmortalFirefly and @SteveEdson
 *
 * @link https://stackoverflow.com/a/28429487/2078474
 */
function buildTree( array &$elements, $parentId = 0 )
{
    $branch = array();
    foreach ( $elements as &$element )
    {
        if ( $element->menu_item_parent == $parentId )
        {
            $children = buildTree( $elements, $element->ID );
            if ( $children )
                $element->wpse_children = $children;

            $branch[$element->ID] = $element;
            unset( $element );
        }
    }
    return $branch;
}

where we added the prefixed wpse_children attribute to avoid name collision.

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 );
    return  $items ? buildTree( $items, 0 ) : null;
}

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

$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 );

For a slightly different version, where we handpicked the attributes, check out the first revision of this answer here.

Update: Walker Class

Here’s a rather sketchy idea how we could try to hook into the recursive part of the the display_element() method of the abstract Walker class.

$w = new WPSE_Nav_Menu_Tree;
$args = (object) [ 'items_wrap' => '', 'depth' => 0, 'walker' => $w ];
$items = wp_get_nav_menu_items( 'my_menu' );
walk_nav_menu_tree( $items, $args->depth, $args );
print_r( $w->branch );  

where WPSE_Nav_Menu_Tree is an extension of the Walker_Nav_Menu class:

class WPSE_Nav_Menu_Tree extends Walker_Nav_Menu
{
   public $branch = [];

   public function display_element($element, &$children, $max_depth, $depth = 0, $args, &$output )
   {
      if( 0 == $depth )
         $this->branch[$element->ID] = $element;

      if ( isset($children[$element->ID] ) )
         $element->wpse_children = $children[$element->ID];

      parent::display_element($element, $children, $max_depth, $depth, $args, $output);
   }
}

This might give us an alternative approach if it works.