trjhtr

I have a program that uses ArrayLists to store a pyramid that has been read by a txt file and calculates the minimum sum value of travelling from the top of the pyramid to the bottom.

My code's main method is like this:

File file1 = new File(args[0]);
Scanner reader = new Scanner(file1); // The Scanner that is going to read file1.
try {
 int pyramidSize = reader.nextInt();
 System.out.println("Pyramid Size = " + pyramidSize);
 ArrayList<ArrayList <Integer>> solution1List = new ArrayList<ArrayList <Integer>>(pyramidSize);

 // Reads all integers to an array list.
 for(int i = 0; i < pyramidSize; i++) 
 solution1List.add(new ArrayList<Integer>());
 
 int row = 0;
 int ctr = 0;
 int rowCounter = 1;

 while(reader.hasNext()) 

 if(reader.hasNextInt()) 

 while(row < rowCounter) 
 int temporaryForSolution1Integer = reader.nextInt();
 solution1List.get(ctr).add(temporaryForSolution1Integer);
 row++;
 
 row = 0;
 ctr++;
 rowCounter++;
 
 else 
 reader.next();
 row++;
 
 

 System.out.println("Triangle size is = " + solution1List.size());
 System.out.println("The minimum sum path is = " + minimumSumPath(solution1List));

And my method for calculating the sum is like this:

public static int minimumSumPath(ArrayList<ArrayList<Integer>> triangle) 

 if (triangle.size() == 0)
 return 0;

 int size = triangle.size();
 int min = Integer.MAX_VALUE;

 int sum = new int[size];
 sum[0] = triangle.get(0).get(0);

 for(int current = 1; current <= size - 1; current++) 
 int next_size = triangle.get(current).size();

 for(int next = next_size - 1; next >= 0; next--) 
 if (next == 0) // Sum[0] gets done by walking the leftmost direct way.
 sum[0] = sum[0] + triangle.get(current).get(next);
 
 else if (next == (next_size - 1)) // Reaches to the rightmost element of that iteration
 sum[next] = sum[next-1] + triangle.get(current).get(next);
 
 else // Provides sum[next] to be the minimal sum that can come there
 sum[next] = Math.min(sum[next-1], sum[next]) + triangle.get(current).get(next);
 
 
 

 for(int i = 0; i < size; i++) 
 if(sum[i] < min) 
 min = sum[i];
 
 
 return min;

My code is working properly. But I wonder if I can do this by implementing with a kind of Tree Data Structure (or other data structure but I thought maybe it could be done with a Tree but I couldn't figure which kind of Tree?). Any advice? I would appreciate any help and recommendation.

I have solved it by creating my own Tree. Here is how it is:

import java.util.LinkedList;
import java.util.Queue;
public class SolutionTree 

 SolutionNode root;

 public SolutionTree() 
 root = null;
 

 public void addRoot(int rootValue) 
 root = new SolutionNode(rootValue);
 

 // New Node Adder
 public void addSolutionNode(int newNodeValue) 
 SolutionNode newNode = new SolutionNode(newNodeValue);
 SolutionNode newNodeRoot = breadth(root);
 if(newNodeRoot.getChildLeft() == null) 
 newNodeRoot.setChildLeft(newNode);
 newNode.setParentLeft(newNodeRoot);
 
 else if(newNodeRoot.getChildRight() == null) 
 newNodeRoot.setChildRight(newNode);
 newNode.setParentLeft(newNodeRoot);
 if(newNodeRoot != root) 
 if(newNodeRoot.getParentLeft().getChildRight().getChildLeft() == null) 
 newNodeRoot.getParentLeft().getChildRight().setChildLeft(newNode);
 newNode.setParentRight(newNodeRoot.getParentLeft().getChildRight());
 
 
 
 

 // Node Class of Solution Tree
 protected class SolutionNode 

 private int value;
 private SolutionNode parentLeft;
 private SolutionNode parentRight;
 private SolutionNode childLeft;
 private SolutionNode childRight;

 // Constructor
 public SolutionNode() 
 value = 0;
 parentLeft = null;
 parentRight = null;
 childLeft = null;
 childRight = null;
 

 // Constructor
 public SolutionNode(int v) 
 value = v;
 parentLeft = null;
 parentRight = null;
 childLeft = null;
 childRight = null;
 

 // MODIFIERS

 public void setValue(int val) 
 value = val;
 

 public void setParentLeft(SolutionNode leftParent) 
 parentLeft = leftParent;
 

 public void setParentRight(SolutionNode rightParent) 
 parentLeft = rightParent;
 

 public void setChildLeft(SolutionNode leftChild) 
 childLeft = leftChild;
 

 public void setChildRight(SolutionNode rightChild) 
 childRight = rightChild;
 

 //ACCESSORS

 public int getValue() 
 return value;
 

 public SolutionNode getParentLeft() 
 return parentLeft;
 

 public SolutionNode getParentRight() 
 return parentRight;
 

 public SolutionNode getChildLeft() 
 return childLeft;
 

 public SolutionNode getChildRight() 
 return childRight;
 




 

 // function to compute the minimum sum path
 // It only returns the sum of the values of nodes on the min sum path 
 int minSumPath(SolutionNode current) 
 if(current == null)
 return 0;

 int sum = current.getValue();

 int left_sum = minSumPath(current.childLeft);
 int right_sum = minSumPath(current.childRight);

 if(left_sum <= right_sum) 
 sum += minSumPath(current.childLeft);
 
 else 
 sum += minSumPath(current.childRight);
 

 return sum;
 

 // Breadth First Traversal
 public static SolutionNode breadth(SolutionNode root) 
 Queue<SolutionNode> queue = new LinkedList<SolutionNode>() ;
 if (root == null)
 return null;
 queue.clear();
 queue.add(root);
 while(!queue.isEmpty())
 SolutionNode node = queue.remove();
 if(node.childLeft != null) 
 queue.add(node.childLeft);
 if(node.childRight != null) 
 queue.add(node.childRight);
 if(node.childLeft == null 
 return null;
 

I am invoking minSumPath at the main of my file reading program.

Have a nice day.