Iterative(non-recursive) preorder traversal of binary tree in Java

In preorder traversal, each node is processed before either of its sub-tree(left and right). Once current node is processed, left sub-tree is processed and control return back to current node and then right sub-tree is processed. In recursive version of preorder traversal stack(LIFO data structure) maintains references of left and right child.
In iterative version of preorder traversal, we need an external stack where references of left and right child is stored so that after visiting left subtree we can process right subtree. The catch here is - first insert right subtree followed by left subtree because, we have to process left subtree first then right subtree.(Insertion in stack should be in opposite order, remember LIFO property of stack).
Algorithm:-
1. Insert root into stack if root is not null.
2. Loop until stack is not empty

1. pop an element from stack  and process its data (Here added in string buffer)
2. If popped elements right and left child exist, push them in stack - right child first followed by left child

3. Do check, for empty state of stack and repeat step 2.
4. On while loop exit. return string with nodes traversal.
Time and space complexity :- Time complexity is order of O(n) and space complexity is O(n).
Refer following binary tree used for preorder traversal.

Preorder traversal output should be :-    12 23 11 56 78 43 18 12 98
Java code Iterative preorder traversal:

public String iterativePreorderTraversal(Node root) {
 /* java.util.Stack */
 Stack<Node> stack = new Stack<>();
 StringBuffer sbf = new StringBuffer();

 if (root != null) {
  /* push root into stack if root is not null */
  stack.push(root);
  /* Loop until stack is not empty */
  while (!stack.isEmpty()) {
   root = stack.pop();
   /* process root data */
   sbf.append(root.getData() + " ");
   Node lc = root.getLeftChild();
   Node rc = root.getRightChild();

   /* If right child exist, push into stack */
   if (rc != null) {
    stack.push(rc);
   }
   /* If left child exist, push into stack */
   if (lc != null) {
    stack.push(lc);
   }
  }// End while loop
 }
 return sbf.toString();
}

Complete sample program for non-recursive preorder traversal in Java

package com.devinline.trees;

import java.util.Stack;

public class IterativePreorderTraversal {

 public String iterativePreorderTraversal(Node root) {
  /* java.util.Stack */
  Stack stack = new Stack<>();
  StringBuffer sbf = new StringBuffer();

  if (root != null) {
   /* push root into stack if root is not null */
   stack.push(root);
   /* Loop until stack is not empty */
   while (!stack.isEmpty()) {
    root = stack.pop();
    /* process root data */
    sbf.append(root.getData() + " ");
    Node lc = root.getLeftChild();
    Node rc = root.getRightChild();

    /* If right child exist, push into stack */
    if (rc != null) {
     stack.push(rc);
    }
    /* If left child exist, push into stack */
    if (lc != null) {
     stack.push(lc);
    }
   }// End while loop
  }
  return sbf.toString();
 }

 public static void main(String[] args) {
  IterativePreorderTraversal itrPreObj = new IterativePreorderTraversal();
  Node root = itrPreObj.new BinaryTree().createTree();
  String nodesStr = itrPreObj.iterativePreorderTraversal(root);
  System.out.println("Iterative preorder traversal:-  " + nodesStr);
 }

 class BinaryTree {
  Node root;

  public BinaryTree() {
   root = null;
  }

  public Node createTree() {
   if (root == null) {
    root = new Node(12);
   }
   root.setLeftChild(new Node(23));
   root.setRightChild(new Node(18));
   root.getLeftChild().setLeftChild(new Node(11));
   root.getLeftChild().setRightChild(new Node(43));
   root.getRightChild().setLeftChild(new Node(12));
   root.getLeftChild().getLeftChild().setLeftChild(new Node(56));
   root.getLeftChild().getLeftChild().setRightChild(new Node(78));
   root.getRightChild().getLeftChild().setRightChild(new Node(98));
   return root;
  }
 }

 class Node {

  private int data;
  private Node leftChild;
  private Node rightChild;

  public Node(int data) {
   this.data = data;
   leftChild = null;
   rightChild = null;
  }

  public int getData() {
   return data;
  }

  public void setData(int data) {
   this.data = data;
  }

  public Node getLeftChild() {
   return leftChild;
  }

  public void setLeftChild(Node leftChild) {
   this.leftChild = leftChild;
  }

  public Node getRightChild() {
   return rightChild;
  }

  public void setRightChild(Node rightChild) {
   this.rightChild = rightChild;
  }
 }

}

============Sample output===============
Iterative preorder traversal:-  12 23 11 56 78 43 18 12 98

======================================