Probléma

Adott egy bináris fa, tervezzen egy algoritmust, amely minden mélységben létrehoz egy linkelt listát az összes csomópontról (pl. ha van egy D mélységű fa, akkor D csatolt listája lesz).

Megoldás

Bár első pillantásra azt gondolhatnánk, hogy ez a probléma szintről-szintre történő bejárást igényel, ez valójában nem szükséges. Bármilyen módon bejárhatjuk a grafikont, feltéve, hogy közben tudjuk, hogy melyik szinten vagyunk.
Megvalósíthatjuk az előrendelési bejárási algoritmus egy egyszerű módosítását, ahol szintet lépünk át. + 1 a következő rekurzív híváshoz. Az alábbi kód egy mélységi keresést használó megvalósítást biztosít.

void createLevelLinkedList(TreeNode root,
                 ArrayList<LinkedList<TreeNode>> lists, int level) {
   if (root == null) return; // base case
   LinkedList<TreeNode> list = null;
   if (lists.size() == level) { // Level not contained in list
      list = new LinkedList<TreeNode>();
      /* Levels are always traversed in order. So., if this is the
      * first time we've visited level i, we must have seen levels
      * 0 through i - 1. We can therefore safely add the level at
      * the end. */
      lists.add(list);
   } else {
      list = lists.get(level);
   }
   list.add(root);
   createLevelLinkedList(root.left, lists, level + 1);
   createLevelLinkedList(root.right, lists, level + 1);
}
ArrayList<LinkedList<TreeNode>> createLevelLinkedList(
                                             TreeNode root) {
   ArrayList<LinkedList<TreeNode>> lists =
                           new ArrayList<LinkedList<TreeNode>>();
   createLevelLinkedList(root, lists, 0);
   return lists;
}