The root is the first node to be visited in preorder. After we visit this node we must traverse the left subtree and then return to traverse the right subtree. To enable the return to the right subtree, we save a pointer to the root of this right subtree on a stack provided the right subtree is not empty. When we are traversing the left subtree of the root, its root is visited a pointer to its nonempty right subtree is saved on the stack, and we proceed to traverse its left subtree. When we are done with the traversal of the left subtree, we move into its right subtree (if it is nonempty) or into the right subtree of the nearest ancestor that has a nonempty right subtree. This is done by removing the right subtree root pointer from the top of the stack. 

 

The stack never contains two pairs that correspond to nodes on the same level. When we reach a leaf the stack contains pointers to nonempty right subtrees of nodes on the path from the root to that leaf. So the stack space needed as well as the overall space needed by the traversal is O(h) where his the height of the binary tree that is being traversed. Notice that when a left-skewed binary tree is traversed nothing is added to the stack.

1.

1 package chapter12Tree; 2  3 import dataStructures.ArrayStack; 4 import dataStructures.BinaryTreeNode; 5  6 public class IterativePreorderTraversal 7 { 8    /** visit method that prints the element in the node */  9    public static void visit(BinaryTreeNode t)10       {System.out.print(t.element + " ");}11 12    /** preorder traversal */13    public static void preOrder(BinaryTreeNode t)14    {15       ArrayStack stack = new ArrayStack(10);16       BinaryTreeNode currentNode = t;17       while (true)18       {
   // traverse subtree rooted at currentNode in preorder19 20          // is subtree empty21          if (currentNode == null)22             // yes it is, get a subtree to traverse from the stack23             try24             {25                currentNode = (BinaryTreeNode) stack.pop();26             }27             catch (Exception e)28             {
   // no untraversed subtrees left29                return;30             }31    32          // first visit the root of the subtree33          visit(currentNode);34    35          // save pointer to right subtree for future traversal36          if (currentNode.rightChild != null)37             stack.push(currentNode.rightChild);38    39          // move into left subtree40          currentNode = currentNode.leftChild;41       }42    }43 }

 

2.

1 /** a stack class that uses a one-dimensional array */ 2  3 package dataStructures; 4  5 import java.util.EmptyStackException; 6 import utilities.*; 7  8 public class ArrayStack implements Stack 9 {10    // data members11    int top;          // current top of stack12    Object [] stack;  // element array13 14    // constructors15    /** create a stack with the given initial capacity16      * @throws IllegalArgumentException when initialCapacity < 1 */17    public ArrayStack(int initialCapacity)18    {19       if (initialCapacity < 1)20          throw new IllegalArgumentException21                ("initialCapacity must be >= 1");22       stack = new Object [initialCapacity];23       top = -1;24    }25 26    /** create a stack with initial capacity 10 */27    public ArrayStack()28       {
   this(10);}29 30    // methods31    /** @return true iff stack is empty */32    public boolean empty()33       {
   return top == -1;}34 35 36    /** @return top element of stack37      * @throws EmptyStackException when the stack is empty */38    public Object peek()39    {40       if (empty())41          throw new EmptyStackException();42       return stack[top];43    }44 45    /** add theElement to the top of the stack */46    public void push(Object theElement)47    {48       // increase array size if necessary49       if (top == stack.length - 1)50          stack = ChangeArrayLength.changeLength1D(stack, 2 * stack.length);51          52       // put theElement at the top of the stack53       stack[++top] = theElement;54    }55 56    /** remove top element of stack and return it57      * @throws EmptyStackException when the stack is empty */58    public Object pop()59    {60       if (empty())61          throw new EmptyStackException();62       Object topElement = stack[top];63       stack[top--] = null;   // enable garbage collection64       return topElement;65    }66    67    /** test program */68    public static void main(String [] args)69    {  70       int x;71       ArrayStack s = new ArrayStack(3);72       // add a few elements73       s.push(new Integer(1));74       s.push(new Integer(2));75       s.push(new Integer(3));76       s.push(new Integer(4));77 78 79       // delete all elements80       while (!s.empty())81       {82          System.out.println("Top element is " + s.peek());83          System.out.println("Removed the element " + s.pop());84       }85    }  86 }

 

3.

1 /** class for nodes used in a binary tree */ 2  3 package dataStructures; 4  5 public class BinaryTreeNode 6 { 7    // package visible data members 8    public Object element; 9    public BinaryTreeNode leftChild;    // left subtree10    public BinaryTreeNode rightChild;   // right subtree11    12    // constructors13    public BinaryTreeNode() {}14         15    public BinaryTreeNode(Object theElement)16       {element = theElement;}17         18    public BinaryTreeNode(Object theElement,19                          BinaryTreeNode theleftChild,20                          BinaryTreeNode therightChild)21    {22        element = theElement;23        leftChild = theleftChild;24        rightChild = therightChild;25    }26 27    // accessor methods28    public BinaryTreeNode getLeftChild() {
   return leftChild;}29    public BinaryTreeNode getRightChild() {
   return rightChild;}30    public Object getElement() {
   return element;}31 32    // mutator methods33    public void setLeftChild(BinaryTreeNode theLeftChild)34       {leftChild = theLeftChild;}35    public void setRightChild(BinaryTreeNode theRightChild)36       {rightChild = theRightChild;}37    public void setElement(Object theElement)38       {element = theElement;}39 40    // output method41    public String toString()42       {
   return element.toString();}43 }

 

4.

1 /** Change the length of an array by creating 2   * a new array of the desired length and copying 3   * elements from the old array to the new one. */ 4 package utilities; 5  6 import wrappers.*; 7 import java.lang.reflect.*; 8  9 public class ChangeArrayLength 10 {11    /** Change the length of the 1D array a.12      * @param n number of elements in a13      * @param newLength new length of array14      * @return array of length newLength with a[0:n-1] copied into it */15    public static Object [] changeLength1D(Object [] a,16                                  int n, int newLength)17    {18       // make sure new length is adequate19       if (n > newLength)20          throw new IllegalArgumentException21                    ("new length is too small");22    23       // allocate a new array of desired length and same type24       Object [] newArray = (Object []) Array.newInstance25                 (a.getClass().getComponentType(), newLength);26    27       // copy from old space to new space28       System.arraycopy(a, 0, newArray, 0, n);29    30       return newArray;31    }32 33    /* Change the length of a 1D array with a.length elements */34    public static Object [] changeLength1D(Object [] a, int newLength)35       {
   return changeLength1D(a, a.length, newLength);}36 37    /** test program */38    public static void main(String [] args)39    {40       // create an array of length 441       MyInteger [] x = {
   new MyInteger(10),42                         new MyInteger(11),43                         new MyInteger(12),44                         new MyInteger(13)};45 46       // output47       System.out.println("Array length is " + x.length);48       System.out.print("The elements are ");49       for (int i = 0; i < 4; i++)50          System.out.print(x[i] + " ");51       System.out.println();52    53       // increase array length to 854       x = (MyInteger []) changeLength1D(x, 8);55    56       // add two elements to x57       for (int i = 4; i < 6; i++)58          x[i] = new MyInteger(10 + i);59    60       // output61       System.out.println("Array length is " + x.length);62       System.out.print("The elements are ");63       for (int i = 0; i < 6; i++)64          System.out.print(x[i] + " ");65       System.out.println();66 67       // increase length to 1068       x = (MyInteger []) changeLength1D(x, 6, 10);69    70       // add four elements to x71       for (int i = 6; i < 10; i++)72          x[i] = new MyInteger(10 + i);73    74       // output75       System.out.println("Array length is " + x.length);76       System.out.print("The elements are ");77       for (int i = 0; i < 10; i++)78          System.out.print(x[i] + " ");79       System.out.println();80 81       // reduce length to 5 retaining only first 3 elements82       x = (MyInteger []) changeLength1D(x, 3, 5);83    84       // output85       System.out.println("Array length is " + x.length);86       System.out.print("The elements are ");87       for (int i = 0; i < 4; i++)88          System.out.print(x[i] + " ");89       System.out.println();90    }91 }