HackerRank Java- Visitor Pattern




In this challenge, we treat the internal implementation of the tree as being closed to modification, so we cannot directly modify it; however, as with real-world situations, the implementation is written in such a way that it allows external classes to extend and build upon its functionality. More specifically, it allows objects of the TreeVis class (a Visitor Design Pattern) to visit the tree and traverse the tree structure via the accept method.

There are two parts to this challenge.



  1. import java.util.ArrayList;
  2. import java.io.*;
  3. import java.util.*;
  4. import java.text.*;
  5. import java.math.*;
  6. import java.util.regex.*;
  7. enum Color {
  8. RED, GREEN
  9. }
  10. abstract class Tree {
  11. private int value;
  12. private Color color;
  13. private int depth;
  14. public Tree(int value, Color color, int depth) {
  15. this.value = value;
  16. this.color = color;
  17. this.depth = depth;
  18. }
  19. public int getValue() {
  20. return value;
  21. }
  22. public Color getColor() {
  23. return color;
  24. }
  25. public int getDepth() {
  26. return depth;
  27. }
  28. public abstract void accept(TreeVis visitor);
  29. }
  30. class TreeNode extends Tree {
  31. private ArrayList<Tree> children = new ArrayList<>();
  32. public TreeNode(int value, Color color, int depth) {
  33. super(value, color, depth);
  34. }
  35. public void accept(TreeVis visitor) {
  36. visitor.visitNode(this);
  37. for (Tree child : children) {
  38. child.accept(visitor);
  39. }
  40. }
  41. public void addChild(Tree child) {
  42. children.add(child);
  43. }
  44. }
  45. class TreeLeaf extends Tree {
  46. public TreeLeaf(int value, Color color, int depth) {
  47. super(value, color, depth);
  48. }
  49. public void accept(TreeVis visitor) {
  50. visitor.visitLeaf(this);
  51. }
  52. }
  53. abstract class TreeVis
  54. {
  55. public abstract int getResult();
  56. public abstract void visitNode(TreeNode node);
  57. public abstract void visitLeaf(TreeLeaf leaf);
  58. }
  59. class SumInLeavesVisitor extends TreeVis {
  60. private int result = 0;
  61. public int getResult() {
  62. return result;
  63. }
  64. public void visitNode(TreeNode node) {
  65. // do nothing
  66. }
  67. public void visitLeaf(TreeLeaf leaf) {
  68. result += leaf.getValue();
  69. }
  70. }
  71. class ProductOfRedNodesVisitor extends TreeVis {
  72. private long result = 1;
  73. private final int M = 1000000007;
  74. public int getResult() {
  75. return (int) result;
  76. }
  77. public void visitNode(TreeNode node) {
  78. if (node.getColor() == Color.RED) {
  79. result = (result * node.getValue()) % M;
  80. }
  81. }
  82. public void visitLeaf(TreeLeaf leaf) {
  83. if (leaf.getColor() == Color.RED) {
  84. result = (result * leaf.getValue()) % M;
  85. }
  86. }
  87. }
  88. class FancyVisitor extends TreeVis {
  89. private int nonLeafEvenDepthSum = 0;
  90. private int greenLeavesSum = 0;
  91. public int getResult() {
  92. return Math.abs(nonLeafEvenDepthSum - greenLeavesSum);
  93. }
  94. public void visitNode(TreeNode node) {
  95. if (node.getDepth() % 2 == 0) {
  96. nonLeafEvenDepthSum += node.getValue();
  97. }
  98. }
  99. public void visitLeaf(TreeLeaf leaf) {
  100. if (leaf.getColor() == Color.GREEN) {
  101. greenLeavesSum += leaf.getValue();
  102. }
  103. }
  104. }
  105. public class Solution {
  106. private static int [] values;
  107. private static Color [] colors;
  108. private static HashMap<Integer, HashSet<Integer>> map;
  109. public static Tree solve() {
  110. Scanner scan = new Scanner(System.in);
  111. int numNodes = scan.nextInt();
  112. /* Save nodes and colors */
  113. values = new int[numNodes];
  114. colors = new Color[numNodes];
  115. map = new HashMap(numNodes);
  116. for (int i = 0; i < numNodes; i++) {
  117. values[i] = scan.nextInt();
  118. }
  119. for (int i = 0; i < numNodes; i++) {
  120. colors[i] = scan.nextInt() == 0 ? Color.RED : Color.GREEN;
  121. }
  122. /* Save edges */
  123. for (int i = 0; i < numNodes - 1; i++) {
  124. int u = scan.nextInt();
  125. int v = scan.nextInt();
  126. /* Edges are undirected: Add 1st direction */
  127. HashSet<Integer> uNeighbors = map.get(u);
  128. if (uNeighbors == null) {
  129. uNeighbors = new HashSet();
  130. map.put(u, uNeighbors);
  131. }
  132. uNeighbors.add(v);
  133. /* Edges are undirected: Add 2nd direction */
  134. HashSet<Integer> vNeighbors = map.get(v);
  135. if (vNeighbors == null) {
  136. vNeighbors = new HashSet();
  137. map.put(v, vNeighbors);
  138. }
  139. vNeighbors.add(u);
  140. }
  141. scan.close();
  142. /* Handle 1-node tree */
  143. if (numNodes == 1) {
  144. return new TreeLeaf(values[0], colors[0], 0);
  145. }
  146. /* Create Tree */
  147. TreeNode root = new TreeNode(values[0], colors[0], 0);
  148. addChildren(root, 1);
  149. return root;
  150. }
  151. private static void addChildren(TreeNode parent, Integer parentNum) {
  152. for (Integer treeNum : map.get(parentNum)) {
  153. map.get(treeNum).remove(parentNum);
  154. HashSet<Integer> grandChildren = map.get(treeNum);
  155. boolean childHasChild
Please click on the like button if it worked

Solution not working or have any suggestions? Please send an email to [email protected]


donate a cup of tea :)


Join Our Facebook Group

Share this solution






codesadda.com

Codesadda.com is your home of programming solutions, tutorials, video tutorials and much more. Sign Up for our weekly newsletter to get update about new content.

Like us on Facebook | Connect with us on LinkedIn | Subscribe our Channel on Youtube