Level-order traversal

O(n)

Level-order průchod prochází strom do šířky: navštíví kořen, pak všechny uzly o úroveň níž, pak další úroveň a tak dál. Místo rekurze používá frontu (vyjmi uzel, zařaď jeho potomky) a takhle se strom vypisuje po úrovních nebo se hledá nejmělčí uzel.

Binární vyhledávací strom
Stiskni ▶ a spusť
Uprav vstup a stiskni Přehrát

Jak to funguje

  1. Vlož kořen do fronty.
  2. Vyjmi uzel a navštiv ho.
  3. Zařaď jeho levého, pak pravého potomka.
  4. Opakuj, dokud není fronta prázdná — uzly vyjdou po úrovních.

Pseudokód

1levelOrder(root):                   # O(n)2  queue ← [root]3  while queue is not empty:4    node ← queue.dequeue()5    visit(node)6    enqueue node.left, node.right     # next level