Added both recursive and non-recursive implementation

varunu28 · web-flow · commit 259ec48a0fe9 · 2021-08-17T08:23:17.000-07:00
diff --git a/Medium/Count Good Nodes in Binary Tree.java b/Medium/Count Good Nodes in Binary Tree.java
@@ -16,18 +16,50 @@
 class Solution {
   public int goodNodes(TreeNode root) {
     int[] count = {0};
-    helper(root, root.val, count);
+    getGoodNodesCountRecursive(root, Integer.MIN_VALUE, count);
     return count[0];
   }
   
-  private void helper(TreeNode root, int currMax, int[] count) {
+  private void getGoodNodesCountRecursive(TreeNode root, int currMax, int[] count) {
     if (root == null) {
       return;
     }
     if (root.val >= currMax) {
       count[0]++;
     }
-    helper(root.left, Math.max(currMax, root.val), count);
-    helper(root.right, Math.max(currMax, root.val), count);
+    getGoodNodesCountRecursive(root.left, Math.max(currMax, root.val), count);
+    getGoodNodesCountRecursive(root.right, Math.max(currMax, root.val), count);
+  }
+  
+  private int getGoodNodesCountNonRecursive(TreeNode root) {
+    if (root == null) {
+      return 0;
+    }
+    int count = 0;
+    Queue<TreePair> queue = new LinkedList<>();
+    queue.add(new TreePair(root, Integer.MIN_VALUE));
+    while (!queue.isEmpty()) {
+      TreePair removed = queue.remove();
+      if (removed.node.val >= removed.currMax) {
+        count++;
+      }
+      if (removed.node.left != null) {
+        queue.add(new TreePair(removed.node.left, Math.max(removed.node.val, removed.currMax)));
+      }
+      if (removed.node.right != null) {
+        queue.add(new TreePair(removed.node.right, Math.max(removed.node.val, removed.currMax)));
+      }
+    }
+    return count;
+  }
+  
+  class TreePair {
+    int currMax;
+    TreeNode node;
+
+    public TreePair(TreeNode node, int currMax) {
+      this.currMax = currMax;
+      this.node = node;
+    }
   }
 }
