iterative depth-first traversal post-order

depth-first traveral 은 크게 pre-order / in-order / post-order tranversal 로 나누어 진다. 이 중 in-order 는 children 의 개수에 따라 정의가 애매하므로 pre-order 와 post-order 만 정리해 보도록 한다.

pre-order depth-first traversal

recursive algorithm:

do_explorer
  set node visited
  do something
  for each children of the node
    call do_explorer


iterative algorithm:

do_explorer
  create a stack
  push node
  while stack is not empty
    pop node
    set node visited
    do something
    for each children of the node
      push child into stack if child is not visited


post-order depth-first traversal

recursive algorithm:

do_explorer
  set node visited
  for each children of the node
    call do_explorer
  do something


iterative algorithm:

do_explorer
  create a stack
  push node
  while stack is not empty
    peek a node
    if all children of the node is processed
       pop the node
       do something
    else 
       process next sibling of the node (push stack if not visited yet)