leetcode

commit 058571160e628a1f5a7fd91f5112d43b4c2c7800
parent a9cb95245c4fc3c0732ccf6cdde7cfcaa80226c2
Author: AndrewLockVI <andrewlaack1@gmail.com>
Date:   Tue, 13 Jun 2023 19:16:27 -0500

Completed minimum difference in bst

Diffstat:
A
minimum-absolute-difference-in-bst/min-diff-in-bst.dart
 | 
34
++++++++++++++++++++++++++++++++++

1 file changed, 34 insertions(+), 0 deletions(-)
diff --git a/minimum-absolute-difference-in-bst/min-diff-in-bst.dart b/minimum-absolute-difference-in-bst/min-diff-in-bst.dart
@@ -0,0 +1,34 @@
+//Given a tree return the minimum difference between any
+//two nodes in the tree. To solve I first traversed the tree and placed all
+//vals into a list. I could have done in order so I did not need to sort, but
+//really it does not speed this up much. I then did a greedy algorithm to iterate
+//through the sorted list to find the smallest difference in the list and returned 
+//that value.
+
+//Time: 306ms Beats: 100%
+//Memory: 148.9MB Beats: 100%
+
+class Solution {
+    List<int> vals = [];
+
+    int getMinimumDifference(TreeNode? root) {
+        recurse(root);
+        vals.sort();
+        int min = 10000000;
+        for (int i = 1; i < vals.length; ++i) {
+            if (vals[i] - vals[i - 1] < min) {
+                min = vals[i] - vals[i - 1];
+            }
+        }
+        return min;
+    }
+
+    void recurse(TreeNode? root) {
+        if (root == null) {
+            return;
+        }
+        vals.add(root.val);
+        recurse(root.right);
+        recurse(root.left);
+    }
+}