Iterative Preorder Traversal

Preorder traversal is easy when you consider recursive approach but it's quite tricky without recursion. The idea is to simulate recursion using stack. Start from the root and put the root's right and left child on the stack respectively. Then pop the topmost element from the stack, visit it and then again put it's right and left child on the stack if they exists. Continue this till the stack is empty.

  
void preorder_traversal(Node *root) {
 if(root == 0)
  return;

 std::vector stack;
 stack.push_back(root);
 Node *current;
 
 while ( !stack.empty()) {
  current = stack.back();
  stack.pop_back();
  
  std::cout << current->value_ << std::endl;
  
  if(current->right_ != NULL)
   stack.push_back(current->right_);
  if(current->left_ != NULL)
   stack.push_back(current->left_);
 }
}