leetcode

commit 0036fa24a145507281f9dc41620bda9b137ce2df
parent b9512011fe817ddb7061d8446411bdeecbdbd0b4
Author: AndrewLockVI <andrewlaack1@gmail.com>
Date:   Thu, 11 May 2023 11:00:18 -0500

Completed validate binary search tree

Diffstat:
A
validate-binary-search-tree/validate-binary-search-tree.dart
 | 
35
+++++++++++++++++++++++++++++++++++

1 file changed, 35 insertions(+), 0 deletions(-)
diff --git a/validate-binary-search-tree/validate-binary-search-tree.dart b/validate-binary-search-tree/validate-binary-search-tree.dart
@@ -0,0 +1,35 @@
+//Return true if the binary search tree is valid and false
+//if it is not.
+//To tell if it is valid verify that the left node is always
+//less than the root node, and the right node is always greater than
+//the root node.
+//My solution uses an inorder search of the tree to first get a list
+//of the nodes in order. Then, I go through the list checking if they are 
+//actually in order and if they are not return false.
+//The time complexity of this code is O(n) where n is the number
+//of nodes in the list.
+//Time: 294MB Beats: 40.91%
+//Memory: 146.6MB Beats: 15.91%
+class Solution {
+  List<int> order_vals = [];
+  bool isValidBST(TreeNode? root) {
+      recurse(root);
+      int last = order_vals[0];
+      for(int i = 1 ; i < order_vals.length ; ++i){
+          if(order_vals[i] <= last){
+              return false;
+          }
+          last = order_vals[i];
+      }
+      return true;
+
+  }
+  void recurse(TreeNode? root){
+      if(root == null){
+          return;
+      }
+      recurse(root.left);
+      order_vals.add((root?.val ?? 0));
+      recurse(root.right);
+  }
+}