Adding Iterative Tree Traversal APIs

BIO2CS · BIO2CS · commit fbbb976bedd2 · 2015-08-03T18:48:56.000-07:00
diff --git a/BinarySearchTree/BST.java b/BinarySearchTree/BST.java
@@ -4,14 +4,15 @@
 import java.util.LinkedList;
 import java.util.List;
 import java.util.Queue;
+import java.util.Stack;
 
 public class BST {
     TreeNode root;
     
     public BST() {        
     }
     
-    public void Insert(int key) {
+    public void insert(int key) {
         TreeNode node = new TreeNode(key);
         TreeNode pre = null, runner = root;
         while (runner != null) {
@@ -170,4 +171,72 @@ public void printTree() {
             }
         }
     }
+    
+    private void printUtil(List<Integer> list, String traversalType) {
+        System.out.println("Binary Search Tree Iterative " + traversalType + " Traversal");
+        for (int d : list) {
+            System.out.print(d + " ");
+        }
+        System.out.println();
+    }
+    
+    public void inorderTraversal() {
+        List<Integer> list = new ArrayList<Integer>();
+        Stack<TreeNode> stack = new Stack<TreeNode>();
+        TreeNode runner = root;
+        while (runner != null || !stack.isEmpty()) {
+            if (runner != null) {
+                stack.push(runner);
+                runner = runner.left;
+            }
+            else {
+                TreeNode top = stack.pop();
+                list.add(top.key);
+                runner = top.right;
+            }
+        }
+        printUtil(list, "Inorder");
+    }
+    
+    public void preorderTraversal() {
+        List<Integer> list = new ArrayList<Integer>();
+        Stack<TreeNode> stack = new Stack<TreeNode>();
+        TreeNode runner = root;
+        while (runner != null || !stack.isEmpty()) {
+            if (runner != null) {
+                list.add(runner.key);
+                if (runner.right != null) {
+                    stack.add(runner.right);
+                }
+                runner = runner.left;
+            }
+            else {
+                runner = stack.pop();
+            }            
+        }
+        printUtil(list, "Preorder");
+    }
+    
+    public void postorderTraversal() {
+        List<Integer> list = new ArrayList<Integer>();
+        Stack<TreeNode> stack = new Stack<TreeNode>();
+        TreeNode runner = root, pre = null;
+        while (runner != null || !stack.isEmpty()) {
+            if (runner != null) {
+                stack.push(runner);
+                runner = runner.left;
+            }
+            else {
+                TreeNode top = stack.peek();
+                if (top.right == null || top.right == pre) {
+                    list.add(top.key);
+                    pre = stack.pop();
+                }
+                else {
+                    runner = top.right;
+                }
+            }
+        }
+        printUtil(list, "Postorder");
+    }
 }
diff --git a/BinarySearchTree/TestClient.java b/BinarySearchTree/TestClient.java
@@ -5,19 +5,24 @@ public class TestClient {
     public static void main(String[] args) {
         //using example on page 263 in CLRS
         BST bst = new BST();
-        bst.Insert(15);
-        bst.Insert(5);
-        bst.Insert(3);
-        bst.Insert(12);
-        bst.Insert(10);
-        bst.Insert(13);
-        bst.Insert(6);
-        bst.Insert(7);
-        bst.Insert(16);
-        bst.Insert(20);
-        bst.Insert(18);
-        bst.Insert(23);
-     //   bst.printTree();
+        bst.insert(15);
+        bst.insert(5);
+        bst.insert(3);
+        bst.insert(12);
+        bst.insert(10);
+        bst.insert(13);
+        bst.insert(6);
+        bst.insert(7);
+        bst.insert(16);
+        bst.insert(20);
+        bst.insert(18);
+        bst.insert(23);
+        
+        bst.inorderTraversal();
+        bst.preorderTraversal();
+        bst.postorderTraversal();
+        
+        //bst.printTree();
         
         TreeNode key = bst.search(15);
         TreeNode next = bst.getPredecessor(key);
diff --git a/BinarySearchTree/TreeNode.java b/BinarySearchTree/TreeNode.java
@@ -1,7 +1,6 @@
 package BinarySearchTree;
 
 public class TreeNode {
-
     int key;
     TreeNode left, right, parent;
     
