Sales path - breadth first - very good performance

SalesPath_breadthFirst.java

import java.io.*;
import java.util.*;

class Solution {
 
  static class Node {
      
    int cost;
    Node[] children;
    Node parent;

    Node(int cost) {
      this.cost = cost;
      children = null;
      parent = null;
    }
  }
  
  static class SalesPath {
       
    static int getCheapestCost(Node rootNode) {
      Queue<Node> q = new ArrayDeque<>();
      Map<Node, Integer> costMap = new HashMap<>();
      q.add(rootNode);
      
      int cheapest = Integer.MAX_VALUE;
      
      while (!q.isEmpty()) 
      {
        Node curNode = q.remove();
        
        // Compute current cost
        int curCost;
        if (curNode.parent != null) 
        {
          curCost = costMap.get(curNode.parent) + curNode.cost;
        } 
        else 
        {
          curCost = curNode.cost;
        }
        
        costMap.put(curNode, curCost);
        
        // If curNode is leaf node, update cheapest
        if (curNode.children == null || curNode.children.length == 0) {
          cheapest = Math.min(cheapest, curCost);
        } else {
          for (Node child : curNode.children) {
            q.add(child);
          } 
        }    
      }
      
      return cheapest;
    }
  }
    
  /*********************************************
   * Driver program to test above method     *
   *********************************************/

  public static void main(String[] args) {    
    Node root = new Node(0);
    Node left = new Node(3);
    Node leftLeaf = new Node(1);
    leftLeaf.parent = left;
    left.parent = root;
    left.children = new Node[]{leftLeaf};
    Node right = new Node(5);
    right.parent = root;
    root.children = new Node[]{left, right};
    
    System.out.println(SalesPath.getCheapestCost(root));   
  }
}