Binary Trees In Java - Non Recursively Revisited

The following is a demonstration of simple Binary Search Tree traversals in Java working off the following diagram. Simple recursive call solutions exist and are often used but they can create a rather large call stack for large binary trees.
Here I've instead favored finding non-recursive solutions for the standard BFS, and 3 types of DFS (preorder, inorder, postorder) which are a little trickier to understand but result in easier memory management for large trees.

To follow along download the 6k source for this article:
TreeTraversal.tar.gz

#unzip:
tar -zxvf TreeTraversal.tar.gz

#configure the eclipse project using maven:
mvn eclipse:eclipse

then simply import as an existing project into eclipse

    1 package Prep.TreeTraversal;
    2 
    3 import java.util.ArrayList;
    4 import java.util.HashSet;
    5 import java.util.LinkedHashSet;
    6 import java.util.List;
    7 import java.util.Queue;
    8 import java.util.Set;
    9 import java.util.Stack;
   10 import java.util.concurrent.ConcurrentLinkedQueue;
   11 
   12 import lombok.ToString;
   13 
   14 import org.apache.log4j.Logger;
   15 
   16 @ToString
   17 public class TreeTraversal {
   18 
   19     private Set<Node> treeNodes = new LinkedHashSet<Node>();
   20     static Logger log = Logger.getLogger(TreeTraversal.class);
   21 
   22     // Node Struct
   23     public class Node {
   24         // -- yes i know public fields - suck it, this is only a Struct.
   25         public Node parent;
   26         public Node self;
   27         public String name;
   28         public Node leftChild;
   29         public Node rightChild;
   30         public Node(String name) {
   31             this.name = name;
   32         }
   33         public String toString() {
   34             return this.name;
   35         }
   36     }
   37 
   38     // traversal methods
   39     //
   40     public List<String> bfsTraversal() {
   41         // basically this uses a queue (first in first out)
   42         // step 1. start by queuing the root node
   43         // step 2. dequeue the first element.
   44         // step 2.5 process it/ add it to the traversal list/ whatever you're
   45         // trying to do
   46         // step 3. enqueue its children in order left then right if they exist.
   47         // step 4. return to step 2 if queue still has elements
   48         Queue<Node> queue = new ConcurrentLinkedQueue<Node>();
   49         queue.add(getRoot());
   50         ArrayList<String> result = new ArrayList<String>();
   51         while (!queue.isEmpty()) {
   52             Node thisNode = queue.remove();
   53             log.debug("processing " + thisNode.name);
   54             result.add(thisNode.name);
   55             if (thisNode.leftChild != null) {
   56                 queue.add(thisNode.leftChild);
   57             }
   58             if (thisNode.rightChild != null) {
   59                 queue.add(thisNode.rightChild);
   60             }
   61         }
   62         return result;
   63     }
   64 
   65     public List<String> dfsPreorderTraversal() {
   66         // uses a stack (last in first out).
   67         // step 1. push the root node
   68         // step 2. pop the next node & process it, print it, whatever you like
   69         // step 3. push the right_child then the left_child if either exist.
   70         // step 4. repeat step 2 till stack is empty.
   71         Stack<Node> mystack = new Stack<Node>();
   72         mystack.push(getRoot());
   73         ArrayList<String> result = new ArrayList<String>();
   74         while (!mystack.isEmpty()) {
   75             Node thisNode = mystack.pop();
   76             log.debug("processing " + thisNode.name);
   77             result.add(thisNode.name);
   78             if (thisNode.rightChild != null) {
   79                 mystack.push(thisNode.rightChild);
   80             }
   81             if (thisNode.leftChild != null) {
   82                 mystack.push(thisNode.leftChild);
   83             }
   84         }
   85         return result;
   86     }
   87 
   88     public List<String> dfsInorderTraversal() {
   89         // uses a stack (last in first out).
   90         // step 1. push the root node and all left sub-children
   91         // step 2. pop the next node & process it, print it, whatever you like
   92         // step 3. if there is a right_child push it and all it's left
   93         // sub-children onto the stack.
   94         // step 4. repeat step 2 till stack is empty.
   95         Stack<Node> mystack = new Stack<Node>();
   96         for (Node node : getAllLeftSubChildresn(getRoot())) {
   97             mystack.push(node);
   98         }
   99         ArrayList<String> result = new ArrayList<String>();
  100         while (!mystack.isEmpty()) {
  101             Node thisNode = mystack.pop();
  102             log.debug("processing " + thisNode.name);
  103             result.add(thisNode.name);
  104             if (thisNode.rightChild != null) {
  105                 for (Node node : getAllLeftSubChildresn(thisNode.rightChild)) {
  106                     mystack.push(node);
  107                 }
  108             }
  109         }
  110         return result;
  111     }
  112 
  113     public List<String> dfsPostorderTraversal() {
  114         // uses a stack (last in first out).
  115         // step 1. push the root node and all left sub-children
  116         // step 2. peek at the top of the stack
  117         // step 3. if that node has an unvisited right_child add it and all its
  118         // left sub-children
  119         // step 4. else pop it, mark it visited and process it.
  120         // step 5. repeat step 2 till stack is empty.
  121 
  122         Stack<Node> mystack = new Stack<Node>();
  123         for (Node node : getAllLeftSubChildresn(getRoot())) {
  124             mystack.push(node);
  125         }
  126         ArrayList<String> result = new ArrayList<String>();
  127         Set<Node> visited = new HashSet<Node>();
  128         Node thisNode;
  129         while (!mystack.isEmpty()) {
  130             thisNode = mystack.peek();
  131             if (thisNode.rightChild != null
  132                     && !visited.contains(thisNode.rightChild)) {
  133                 for (Node node : getAllLeftSubChildresn(thisNode.rightChild)) {
  134                     mystack.push(node);
  135                 }
  136             } else {
  137                 log.debug("processing " + thisNode.name + ", curr stack: "
  138                         + mystack);
  139                 thisNode = mystack.pop();
  140                 visited.add(thisNode);
  141                 result.add(thisNode.name);
  142             }
  143         }
  144         return result;
  145     }
  146 
  147     // Tree helper methods
  148     //
  149     public Node getRoot() {
  150         for (Node node : treeNodes) {
  151             if (node.parent == null) {
  152                 return node;
  153             }
  154         }
  155         throw new RuntimeException("These nodes don't form a valid tree since there is no root");
  156     }
  157 
  158     private List<Node> getAllLeftSubChildresn(Node root) {
  159         ArrayList<Node> result = new ArrayList<Node>();
  160         result.add(root);
  161         while (root.leftChild != null) {
  162             result.add(root.leftChild);
  163             root = root.leftChild;
  164         }
  165         return result;
  166     }
  167 
  168     public Set<Node> getTreeNodes() {
  169         return treeNodes;
  170     }
  171 
  172 }
  173 

And some test cases:

    1 package Prep.TreeTraversal;
    2 
    3 import java.util.Arrays;
    4 import java.util.List;
    5 
    6 import junit.framework.Assert;
    7 
    8 import org.apache.log4j.Logger;
    9 import org.junit.Before;
   10 import org.junit.Test;
   11 
   12 import Prep.TreeTraversal.TreeTraversal.Node;
   13 
   14 public class TreeTraversalTest {
   15 
   16     private TreeTraversal traversal;
   17     static Logger log = Logger.getLogger(TreeTraversalTest.class);
   18 
   19     @Before
   20     public void setUp() {
   21         traversal = new TreeTraversal();
   22 
   23         Node nA = traversal.new Node("A");
   24         Node nB = traversal.new Node("B");
   25         Node nC = traversal.new Node("C");
   26         Node nD = traversal.new Node("D");
   27         Node nE = traversal.new Node("E");
   28         Node nF = traversal.new Node("F");
   29         Node nH = traversal.new Node("H");
   30         Node nG = traversal.new Node("G");
   31         Node nI = traversal.new Node("I");
   32         
   33         nF.leftChild = nB;
   34         nF.rightChild = nG;             
   35         nB.leftChild = nA;
   36         nB.rightChild = nD;
   37         nG.rightChild = nI;
   38         nD.leftChild = nC;
   39         nD.rightChild = nE;
   40         nI.leftChild = nH;
   41         
   42         nA.parent = nB;
   43         nB.parent = nF;
   44         nC.parent = nD;
   45         nD.parent = nB;
   46         nE.parent = nD;
   47         nF.parent = null;
   48         nG.parent = nF;
   49         nH.parent = nI;
   50         nI.parent = nG;
   51         
   52         final Node[] nodesArr = {nA, nB, nC, nD, nE, nF, nG, nH, nI};
   53         traversal.getTreeNodes().addAll((Arrays.asList(nodesArr)));
   54 
   55     }
   56 
   57     @Test
   58     public void testBFS() {
   59         log.debug(traversal);
   60         List<String> actualOrder = traversal.bfsTraversal();
   61         String[] expectedOrder = {"F", "B", "G", "A", "D", "I", "C", "E", "H"};
   62         Assert.assertEquals(Arrays.asList(expectedOrder), actualOrder);
   63 
   64     }
   65     
   66     @Test
   67     public void testDFSPreorder() {
   68         log.debug(traversal);
   69         List<String> actualOrder = traversal.dfsPreorderTraversal();
   70         String[] expectedOrder = {"F", "B", "A", "D", "C", "E", "G", "I", "H"};
   71         Assert.assertEquals(Arrays.asList(expectedOrder), actualOrder);
   72 
   73     }
   74 
   75     @Test
   76     public void testDFSInorder() {
   77         log.debug(traversal);
   78         List<String> actualOrder = traversal.dfsInorderTraversal();
   79         String[] expectedOrder = {"A", "B", "C", "D", "E", "F", "G", "H", "I"};
   80         Assert.assertEquals(Arrays.asList(expectedOrder), actualOrder);
   81 
   82     }
   83     
   84     @Test
   85     public void testDFSPostorder() {
   86         log.debug(traversal);
   87         List<String> actualOrder = traversal.dfsPostorderTraversal();
   88         String[] expectedOrder = {"A", "C", "E", "D", "B", "H", "I", "G", "F"};
   89         Assert.assertEquals(Arrays.asList(expectedOrder), actualOrder);
   90 
   91     }
   92     
   93 }
   94