In-order traversal

O(n)

In-order průchod se zanoří do levého potomka, navštíví uzel a pak se zanoří do pravého. U binárního vyhledávacího stromu vypíše hodnoty seřazeně, proto je in-order výchozí volba pro výpis BST. Běží v O(n) a používá O(h) zásobníku pro výšku h.

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

Jak to funguje

  1. Nejdřív se zanoř do levého podstromu.
  2. Navštiv aktuální uzel.
  3. Zanoř se do pravého podstromu.
  4. U BST vyjdou uzly vzestupně.

Pseudokód

1inorder(node):                      # O(n)2  if node = null: return3  inorder(node.left)4  visit(node)                        # sorted order on a BST5  inorder(node.right)