Post-order traversal

O(n)

Post-order průchod navštíví uzel až po obou podstromech: levý, pak pravý, pak uzel. Protože se potomci zpracují před rodičem, používá se k bezpečnému uvolnění/smazání stromu a k vyhodnocení výrazových stromů (operandy před operátorem).

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

Jak to funguje

  1. Zanoř se do levého podstromu.
  2. Zanoř se do pravého podstromu.
  3. Aktuální uzel navštiv jako poslední.
  4. Potomci se vždy zpracují před rodičem.

Pseudokód

1postorder(node):                    # O(n)2  if node = null: return3  postorder(node.left)4  postorder(node.right)5  visit(node)                        # children before root