I did a slightly different way. I did an in-order traversal, and stored the values in an array. Then i looped over the array, checking if each element was strictly greater than its previous element. This also worked out really well
Best explanation and dry-run/visualization on this problem. Thank you Greg for this one, it looked very complicated until I watched your explanation. There is another less complicated solution - we can do in-order traversal and check if the current node value is greater than the last visited node, because in-order traversal of BST will be sorted. I will have to check that solution too after I code this version in C#
I found printing values in console for each call frame is massively beneficial in understanding what's being passed in each call frame, what are local variable states etc. Also, C# code public class Solution { public bool IsValidBST(TreeNode root) { return IsValidBSTHelper(root, long.MinValue, long.MaxValue); }
is not that easier to use inorder with append to a list and then check for each value in list if it is smaller then the next value (not sure about the efficiency, i would really like to read some comments on this one)
Master Data Structures & Algorithms For FREE at AlgoMap.io!
I did a slightly different way. I did an in-order traversal, and stored the values in an array. Then i looped over the array, checking if each element was strictly greater than its previous element. This also worked out really well
Best explanation and dry-run/visualization on this problem. Thank you Greg for this one, it looked very complicated until I watched your explanation. There is another less complicated solution - we can do in-order traversal and check if the current node value is greater than the last visited node, because in-order traversal of BST will be sorted. I will have to check that solution too after I code this version in C#
That's also a great solution! And thank you very much
Bros actually the GOAT! explains things in a different way fr
So clear and concise
Thanks so much, so glad to hear it!!
I found printing values in console for each call frame is massively beneficial in understanding what's being passed in each call frame, what are local variable states etc.
Also, C# code
public class Solution {
public bool IsValidBST(TreeNode root) {
return IsValidBSTHelper(root, long.MinValue, long.MaxValue);
}
private bool IsValidBSTHelper(TreeNode node, long minVal, long maxVal) {
if (node != null) {
Console.WriteLine("node: " + node.val + " minVal: " + minVal + " MaxVal " + maxVal + "
");
}
if (node == null) {
return true;
}
if (node.val = maxVal) {
return false;
}
return IsValidBSTHelper(node.left, minVal, (long)node.val) && IsValidBSTHelper(node.right, (long)node.val, maxVal);
}
}
-----------------------output for the tree Greg showed------------------------------------------
Your input
[3,1,5,0,2,4,6]
stdout
node: 3 minVal: -9223372036854775808 MaxVal 9223372036854775807
node: 1 minVal: -9223372036854775808 MaxVal 3
node: 0 minVal: -9223372036854775808 MaxVal 1
node: 2 minVal: 1 MaxVal 3
node: 5 minVal: 3 MaxVal 9223372036854775807
node: 4 minVal: 3 MaxVal 5
node: 6 minVal: 5 MaxVal 9223372036854775807
I understood everything after drawing out the tree, and writing down values on paper for each step + printing on the console. Hope it helps someone😊
Thanks. Will the space complexity be O(logn) - height of the tree?
If we assume its balanced, then log n. But the tree could technically be one huge diagonal line for for example making the height n.
@@GregHogg good call!
Awesome explanation
I solved it exactly like this but instead of arguments as min/max, I made the return values as a triplet
Appreciate the video brother
great explanation you're goat
is not that easier to use inorder with append to a list and then check for each value in list if it is smaller then the next value
(not sure about the efficiency, i would really like to read some comments on this one)
this solution works, I did it like that but Greg's solution is faster
Nice