Algorithms Assignment 3

LowestTrav.java

import java.util.Hashtable;

public class LowestTrav {
	
static int nodeVisits = 0;	
static Hashtable<TreeNode, Integer> table = new Hashtable<TreeNode, Integer>();


	public static void main(String args[]){
		TreeNode tree = createTree();
		
		System.out.println("Beginning Traversal");
		int minTraversal = minTrav(4,4, tree);
		System.out.println("Ending Traversal with " + nodeVisits +" visits to a node \n");
		System.out.println("HashTable End Values of Size [" + table.size() + "]");
		System.out.println(table);	
		System.out.println("\n The shortest traversal through the tree is " + minTraversal);
	}
	

	public static int minTrav(int r,int c, TreeNode tree){
		int left = 0, right = 0; 
		int value;
		
		nodeVisits++;
		
		
		if(1 == r){                                 //Base Case *if Children == null*
			table.put(tree, tree.getValue());
			return tree.getValue();
		}
		else{			 //Recursion Case
						//Check if children are add, if not call method on them
			if(table.containsKey(tree.getLeft())){   
				left = table.get(tree.getLeft());
			}
			else{
				left = minTrav(r-1,c,tree.getLeft());
			}
			
			if(table.containsKey(tree.getRight())){   
				right = table.get(tree.getRight());
			}
			else{
				right = minTrav(r-1,c-1,tree.getRight());
			}
			
			value = tree.getValue() + Math.min(left, right);
			table.put(tree, value);
			
			return value;
		}
	}
	
	
	public static TreeNode createTree(){
		TreeNode n14 = new TreeNode(8);
		TreeNode n24 = new TreeNode(6);
		TreeNode n34 = new TreeNode(9);
		TreeNode n44 = new TreeNode(6);
		TreeNode n13 = new TreeNode(1,n14,n24);
		TreeNode n23 = new TreeNode(4,n24,n34);
		TreeNode n33 = new TreeNode(7,n34,n44);
		TreeNode n12 = new TreeNode(5,n13,n23);
		TreeNode n22 = new TreeNode(4,n23,n33);
		TreeNode parent = new TreeNode(2,n12,n22);
				
		return parent;
	}
	
	public static void printTree(TreeNode tree){
		System.out.println(tree.getValue());
		
		if(tree.getLeft() != null){
			printTree(tree.getLeft());
		}
		
		if(tree.getRight() != null){
			printTree(tree.getRight());
		}
	}
}

TreeNode.java

public class TreeNode {
	private int value;
	private TreeNode leftNode;
	private TreeNode rightNode;
	
	public TreeNode(int value){
		this.value = value;
		this.leftNode = null;
		this.rightNode = null;
	}
	
	public TreeNode(int value, TreeNode left, TreeNode right){
		this.value = value;
		this.leftNode = left;
		this.rightNode = right;
	}

	public int getValue() {
		return value;
	}

	public TreeNode getLeft() {
		return leftNode;
	}

	public TreeNode getRight() {
		return rightNode;
	}
	
}