Order

      n

l. r

preorder

n → l → r

recursivePreorder(_ node: Node) {
	if node is nil {
		return
	}
	print(node)
	recursivePreorder(node.left)
	recursivePreorder(node.right)
}

func iterativePreorder(_ node: Node) {
	if node is nil {
		return
	}
  var stack: [Int] = [node]
	while !stack.isEmpty {
		let pop_node = stack.removeLast()
    print(pop_node.val)
    if let r = pop_node.right {
			stack.append(r)
		}
		if let l = pop_node.left {
			stack.append(l)
		}
	}
}

inorder

l→ n→ r

recursiveInorder(_ node: Node) {
	if node is nil {
		return
	}

	recursiveInorder(node.left)
	print(node)
	recursiveInorder(node.right)
}

func iterativeInorder(_ node: Node) {
	if node is nil {
		return
	}
  var stack: [Int] = [node]
  var curNode = node 
	while true {
		if node != nil {
			st.append(curNode)
			curNode = curNode.left
		}
		else if !stack.isEmpty {
			curNode = stack.pop()
			print(curNode.val)
			curNode = curNode.right
		}
		else {
			break
		}
	}
}

postorder

l → r → n

recursivePostorder(_ node: Node) {
	if node is nil {
		return
	}

	recursivePostorder(node.left)
	recursivePostorder(node.right)
	print(node)
}

def iterativePostorder(node):
  stack = []
  last_visit_node = None
  crnt_node = node
  while True:
    if crnt_node is not None:
      stack.append(crnt_node)
      crnt_node = crnt_node.left
    
    elif 0<len(stack):
      peek_node = stack[-1]
      if peek_node.right and last_visit_node != peek_node.right:
        crnt_node = peek_node.right
      else:
        print(peek_node.val, end=' ')
        last_visit_node = stack.pop()
        
    else:
      break