diff --git a/core/includes/menu.inc b/core/includes/menu.inc
index 8844ae5..6aae567 100644
--- a/core/includes/menu.inc
+++ b/core/includes/menu.inc
@@ -435,7 +435,7 @@ function menu_tree_get_path($menu_name) {
  *   same structure described for the top-level array.
  */
 function menu_tree_page_data($menu_name, $max_depth = NULL, $only_active_trail = FALSE) {
-  return \Drupal::service('menu_link.tree')->menu_tree_all_data($menu_name, $max_depth, $only_active_trail);
+  return \Drupal::service('menu_link.tree')->buildAllData($menu_name, $max_depth, $only_active_trail);
 }
 
 /**
diff --git a/core/modules/menu_link/lib/Drupal/menu_link/MenuTree.php b/core/modules/menu_link/lib/Drupal/menu_link/MenuTree.php
index 9bd54c3..c9f69b7 100644
--- a/core/modules/menu_link/lib/Drupal/menu_link/MenuTree.php
+++ b/core/modules/menu_link/lib/Drupal/menu_link/MenuTree.php
@@ -622,7 +622,7 @@ protected function doCheckAccess(&$tree) {
     $new_tree = array();
     foreach ($tree as $key => $v) {
       $item = &$tree[$key]['link'];
-      $this->menuLinkTranslate();
+      $this->menuLinkTranslate($item);
       if ($item['access'] || ($item['in_active_trail'] && strpos($item['href'], '%') !== FALSE)) {
         if ($tree[$key]['below']) {
           $this->doCheckAccess($tree[$key]['below']);
@@ -692,7 +692,7 @@ protected function doBuildTreeData(&$links, $parents, $depth) {
       $next = end($links);
       // Check whether the next link is the first in a new sub-tree.
       if ($next && $next['depth'] > $depth) {
-        // Recursively call _menu_tree_data to build the sub-tree.
+        // Recursively call doBuildTreeData to build the sub-tree.
         $tree[$item['mlid']]['below'] = $this->doBuildTreeData($links, $parents, $next['depth']);
         // Fetch next link after filling the sub-tree.
         $next = end($links);
@@ -709,7 +709,7 @@ protected function menuLinkGetPreferred($menu_name, $active_path) {
     return menu_link_get_preferred($active_path, $menu_name);
   }
 
-  protected function menuLinkTranslate() {
+  protected function menuLinkTranslate(&$item) {
     return _menu_link_translate($item);
   }
 
diff --git a/core/modules/menu_link/menu_link.services.yml b/core/modules/menu_link/menu_link.services.yml
index b225016..8a2c5b2 100644
--- a/core/modules/menu_link/menu_link.services.yml
+++ b/core/modules/menu_link/menu_link.services.yml
@@ -1,4 +1,4 @@
 services:
   menu_link.tree:
     class: Drupal\menu_link\MenuTree
-    arguments: ['@database', '@cache.menu', '@request_stack', '@entity.manager', '@entity.query', '@state']
+    arguments: ['@database', '@cache.menu', '@language_manager', '@request_stack', '@entity.manager', '@entity.query', '@state']
diff --git a/core/modules/menu_link/tests/Drupal/menu_link/Tests/MenuTreeTest.php b/core/modules/menu_link/tests/Drupal/menu_link/Tests/MenuTreeTest.php
index 72f2adc..17f1b94 100644
--- a/core/modules/menu_link/tests/Drupal/menu_link/Tests/MenuTreeTest.php
+++ b/core/modules/menu_link/tests/Drupal/menu_link/Tests/MenuTreeTest.php
@@ -9,6 +9,7 @@
 
 use Drupal\menu_link\MenuTree;
 use Drupal\Tests\UnitTestCase;
+use PHPUnit_Framework_Constraint_IsEqual;
 use Symfony\Component\HttpFoundation\RequestStack;
 
 class MenuTreeTest extends UnitTestCase {
@@ -16,7 +17,7 @@ class MenuTreeTest extends UnitTestCase {
   /**
    * The tested menu tree.
    *
-   * @var \Drupal\menu_link\MenuTree
+   * @var \Drupal\menu_link\MenuTree|\Drupal\menu_link\Tests\TestMenuTree
    */
   protected $menuTree;
 
@@ -29,6 +30,25 @@ class MenuTreeTest extends UnitTestCase {
   protected $state;
 
   /**
+   * Stores some default values for a menu link.
+   *
+   * @var array
+   */
+  protected $defaultMenuLink = array(
+    'menu_name' => 'main-menu',
+    'mlid' => 1,
+    'title' => 'Example 1',
+    'route_name' => 'example1',
+    'link_path' => 'example1',
+    'access' => 1,
+    'hidden' => FALSE,
+    'has_children' => FALSE,
+    'in_active_trail' => TRUE,
+    'localized_options' => array('attributes' => array('title' => '')),
+    'weight' => 0,
+  );
+
+  /**
    * {@inheritdoc}
    */
   protected function setUp() {
@@ -44,7 +64,7 @@ protected function setUp() {
       ->getMock();
     $this->state = $this->getMock('Drupal\Core\KeyValueStore\StateInterface');
 
-    $this->menuTree = new MenuTree($this->connection, $this->cacheBackend, $this->languageManager, $this->requestStack, $this->entityManager, $this->entityQueryFactory, $this->state);
+    $this->menuTree = new TestMenuTree($this->connection, $this->cacheBackend, $this->languageManager, $this->requestStack, $this->entityManager, $this->entityQueryFactory, $this->state);
   }
 
   /**
@@ -62,4 +82,219 @@ public function testActivePaths() {
     $this->assertEquals('example_path2', $this->menuTree->getPath('test_menu2'));
   }
 
-} 
+  /**
+   * Tests buildTreeData with a single level.
+   */
+  public function testBuildTreeDataWithSingleLevel() {
+    $items = array();
+    $items[] = array(
+      'mlid' => 1,
+      'depth' => 1,
+      'route_name' => 'example1',
+    );
+    $items[] = array(
+      'mlid' => 2,
+      'depth' => 1,
+      'route_name' => 'example2',
+    );
+
+    $result = $this->menuTree->buildTreeData($items, array(), 1);
+
+    $this->assertCount(2, $result);
+    $this->assertEquals(array('mlid' => 1, 'depth' => 1, 'route_name' => 'example1', 'in_active_trail' => FALSE), $result[1]['link']);
+    $this->assertEquals(array('mlid' => 2, 'depth' => 1, 'route_name' => 'example2', 'in_active_trail' => FALSE), $result[2]['link']);
+  }
+
+  /**
+   * Tests buildTreeData with a single level and one item being active.
+   */
+  public function testBuildTreeDataWithSingleLevelAndActiveItem() {
+    $items = array();
+    $items[] = array(
+      'mlid' => 1,
+      'depth' => 1,
+      'route_name' => 'example1',
+    );
+    $items[] = array(
+      'mlid' => 2,
+      'depth' => 1,
+      'route_name' => 'example2',
+    );
+
+    $result = $this->menuTree->buildTreeData($items, array(1), 1);
+
+    $this->assertCount(2, $result);
+    $this->assertEquals(array('mlid' => 1, 'depth' => 1, 'route_name' => 'example1', 'in_active_trail' => TRUE), $result[1]['link']);
+    $this->assertEquals(array('mlid' => 2, 'depth' => 1, 'route_name' => 'example2', 'in_active_trail' => FALSE), $result[2]['link']);
+  }
+
+  /**
+   * Tests buildTreeData with a single level and none item being active.
+   */
+  public function testBuildTreeDataWithSingleLevelAndNoActiveItem() {
+    $items = array();
+    $items[] = array(
+      'mlid' => 1,
+      'depth' => 1,
+      'route_name' => 'example1',
+    );
+    $items[] = array(
+      'mlid' => 2,
+      'depth' => 1,
+      'route_name' => 'example2',
+    );
+
+    $result = $this->menuTree->buildTreeData($items, array(3), 1);
+
+    $this->assertCount(2, $result);
+    $this->assertEquals(array('mlid' => 1, 'depth' => 1, 'route_name' => 'example1', 'in_active_trail' => FALSE), $result[1]['link']);
+    $this->assertEquals(array('mlid' => 2, 'depth' => 1, 'route_name' => 'example2', 'in_active_trail' => FALSE), $result[2]['link']);
+  }
+
+  /**
+   * Tests buildTreeData with multiple levels.
+   */
+  public function testBuildTreeDataWithMultipleLevels() {
+    $items = array();
+    $items[] = array(
+      'mlid' => 1,
+      'depth' => 1,
+      'route_name' => 'example1',
+    );
+    $items[] = array(
+      'mlid' => 2,
+      'depth' => 1,
+      'route_name' => 'example2',
+    );
+
+    $result = $this->menuTree->buildTreeData($items, array(3), 1);
+
+    $this->assertCount(2, $result);
+    $this->assertEquals(array('mlid' => 1, 'depth' => 1, 'route_name' => 'example1', 'in_active_trail' => FALSE), $result[1]['link']);
+    $this->assertEquals(array('mlid' => 2, 'depth' => 1, 'route_name' => 'example2', 'in_active_trail' => FALSE), $result[2]['link']);
+  }
+
+  /**
+   * Tests buildTreeData with a more complex example.
+   */
+  public function testBuildTreeWithComplexData() {
+    $items = array(
+      1 => array('mlid' => 1, 'depth' => 1),
+      2 => array('mlid' => 2, 'depth' => 1),
+      3 => array('mlid' => 3, 'depth' => 2),
+      4 => array('mlid' => 4, 'depth' => 3),
+      5 => array('mlid' => 5, 'depth' => 1),
+    );
+
+    $tree = $this->menuTree->buildTreeData($items);
+
+    // Validate that parent items #1, #2, and #5 exist on the root level.
+    $this->assertEquals($items[1]['mlid'], $tree[1]['link']['mlid']);
+    $this->assertEquals($items[2]['mlid'], $tree[2]['link']['mlid']);
+    $this->assertEquals($items[5]['mlid'], $tree[5]['link']['mlid']);
+
+    // Validate that child item #4 exists at the correct location in the hierarchy.
+    $this->assertEquals($items[4]['mlid'], $tree[2]['below'][3]['below'][4]['link']['mlid']);
+  }
+
+  /**
+   * Tests the output with a single level.
+   */
+  public function testOutputWithSingleLevel() {
+    $tree = array(
+      '1' => array(
+        'link' => array('mlid' => 1) + $this->defaultMenuLink,
+        'below' => array(),
+      ),
+      '2' => array(
+        'link' => array('mlid' => 2) + $this->defaultMenuLink,
+        'below' => array(),
+      ),
+    );
+
+    $output = $this->menuTree->output($tree);
+
+    // Validate that the - in main-menu is changed into an underscore
+    $this->assertEquals($output['1']['#theme'], 'menu_link__main_menu', 'Hyphen is changed to an underscore on menu_link');
+    $this->assertEquals($output['2']['#theme'], 'menu_link__main_menu', 'Hyphen is changed to an underscore on menu_link');
+    $this->assertEquals($output['#theme_wrappers'][0], 'menu_tree__main_menu', 'Hyphen is changed to an underscore on menu_tree wrapper');
+  }
+
+  /**
+   * Tests the output method with a complex example.
+   */
+  public function testOutputWithComplexData() {
+    $tree = array(
+      '1'=> array(
+        'link' => array('mlid' => 1, 'has_children' => 1, 'title' => 'Item 1', 'link_path' => 'a') + $this->defaultMenuLink,
+        'below' => array(
+          '2' => array('link' => array('mlid' => 2, 'title' => 'Item 2', 'link_path' => 'a/b') + $this->defaultMenuLink,
+            'below' => array(
+              '3' => array('link' => array('mlid' => 3, 'title' => 'Item 3', 'in_active_trail' => 0, 'link_path' => 'a/b/c') + $this->defaultMenuLink,
+                'below' => array()),
+              '4' => array('link' => array('mlid' => 4, 'title' => 'Item 4', 'in_active_trail' => 0, 'link_path' => 'a/b/d') + $this->defaultMenuLink,
+                'below' => array())
+            )
+          )
+        )
+      ),
+      '5' => array('link' => array('mlid' => 5, 'hidden' => 1, 'title' => 'Item 5', 'link_path' => 'e') + $this->defaultMenuLink, 'below' => array()),
+      '6' => array('link' => array('mlid' => 6, 'title' => 'Item 6', 'in_active_trail' => 0, 'access' => 0, 'link_path' => 'f') + $this->defaultMenuLink, 'below' => array()),
+      '7' => array('link' => array('mlid' => 7, 'title' => 'Item 7', 'in_active_trail' => 0, 'link_path' => 'g') + $this->defaultMenuLink, 'below' => array())
+    );
+
+    $output = $this->menuTree->output($tree);
+
+    // Looking for child items in the data
+    $this->assertEquals( $output['1']['#below']['2']['#href'], 'a/b', 'Checking the href on a child item');
+    $this->assertTrue(in_array('active-trail', $output['1']['#below']['2']['#attributes']['class']), 'Checking the active trail class');
+    // Validate that the hidden and no access items are missing
+    $this->assertFalse(isset($output['5']), 'Hidden item should be missing');
+    $this->assertFalse(isset($output['6']), 'False access should be missing');
+    // Item 7 is after a couple hidden items. Just to make sure that 5 and 6 are skipped and 7 still included
+    $this->assertTrue(isset($output['7']), 'Item after hidden items is present');
+  }
+
+  /**
+   * Tests menu tree access check with a single level.
+   */
+  public function testCheckAccessWithSingleLevel() {
+    $items = array(
+      array('mlid' => 1, 'route_name' => 'menu_test_1', 'depth' => 1, 'link_path' => 'menu_test/test_1', 'in_active_trail' => FALSE) + $this->defaultMenuLink,
+      array('mlid' => 2, 'route_name' => 'menu_test_2', 'depth' => 1, 'link_path' => 'menu_test/test_2', 'in_active_trail' => FALSE) + $this->defaultMenuLink,
+    );
+
+    // Register a menuLinkTranslate to mock the access.
+    $this->menuTree->menuLinkTranslateCallable = function(&$item) {
+      $item['access'] = $item['mlid'] == 1;
+    };
+
+    // Build the menu tree and check access for all of the items.
+    $tree = $this->menuTree->buildTreeData($items);
+    $this->menuTree->checkAccess($tree);
+
+    $this->assertCount(1, $tree);
+    $item = reset($tree);
+    $this->assertEquals($items[0], $item['link']);
+  }
+
+}
+
+class TestMenuTree extends MenuTree {
+
+  /**
+   * An alternative callable used for menuLinkTranslate.
+   * @var callable
+   */
+  public $menuLinkTranslateCallable;
+
+  protected function menuLinkTranslate(&$item) {
+    if (isset($this->menuLinkTranslateCallable)) {
+      call_user_func_array($this->menuLinkTranslateCallable, array(&$item));
+    }
+  }
+
+  protected function menuLinkGetPreferred($menu_name, $active_path) {
+  }
+
+}