Validate Binary Search Tree - Leetcode 98 - Trees (Python)

Master Data Structures & Algorithms for FREE at AlgoMap.io/
Code solutions in Python, Java, C++ and JS for this can be found at my GitHub repo here: github.com/gah...
Complete DSA Pathway Zero to Hero: • Data Structures & Algo...
Please check my playlists for free DSA problem solutions:
• Fundamental DSA Theory
• Array & String Questions
• 2 Pointers Questions
• Sliding Window Questions
• Binary Search Questions
• Stack Questions
• Linked List Questions
• Tree Questions
• Heap Questions
• Recursive Backtracking...
• Graph Questions
• Dynamic Programming (D...
My Data Science & ML RUclips Playlist: • Greg's Path to Become ...
Learn Python and Data Science FASTER at mlnow.ai :)
Support the content: / @greghogg
Follow me on Instagram: / greghogg5
Connect with me on LinkedIn: / greghogg
Follow me on TikTok: / greghogg5
Coursera Plus: imp.i384100.ne...
My Favorite Courses:
Data Structures & Algorithms:
- UCalifornia San Diego DSA: imp.i384100.ne...
- Stanford Algorithms: imp.i384100.ne...
- Python Data Structures: imp.i384100.ne...
- Meta Coding Interview Prep: imp.i384100.ne...
Python:
- UMichigan Python for Everybody: imp.i384100.ne...
- Python Mastery from MLNOW.ai: mlnow.ai/cours...
- Google IT Automation w/ Python: imp.i384100.ne...
Web Dev / Full Stack:
- Meta Front-End Developer: imp.i384100.ne...
- IBM Full Stack Developer: imp.i384100.ne...
- Meta Back-End Developer: imp.i384100.ne...
- John Hopkins HTML, CSS & JS: imp.i384100.ne...
- IBM DevOps: imp.i384100.ne...
Cloud Development:
- AWS Fundamentals: imp.i384100.ne...
- GCP Cloud Engineer: imp.i384100.ne...
- Microsoft Azure Fundamentals: imp.i384100.ne...
Game Development:
- Michigan State Unity Development: imp.i384100.ne...
- UColorado C++ for Unreal Engine: www.coursera.o...
SQL & Data Science:
- SQL by MLNOW.ai: mlnow.ai/cours...
- Python for Data Science by MLNOW.ai: mlnow.ai/cours...
- Google Data Analytics: imp.i384100.ne...
- IBM Data Science: imp.i384100.ne...
- IBM Data Engineer: imp.i384100.ne...
Machine Learning & AI:
- ML Mastery at MLNOW.ai: mlnow.ai/cours...
- ML w/ Andrew Ng: www.coursera.o...
- Deep Learning w/ Andrew Ng: imp.i384100.ne...

[@GregHogg]

Master Data Structures & Algorithms For FREE at AlgoMap.io!

[@__chroma__8660]

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

[@noextrasugar]

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#

[@GregHogg]

That's also a great solution! And thank you very much

[@kiritosv8825]

So clear and concise

[@GregHogg]

Thanks so much, so glad to hear it!!

[@saurabhbhagat4528]

I solved it exactly like this but instead of arguments as min/max, I made the return values as a triplet

[@abdlaboda8443]

great explanation you're goat

[@DanikDemchuk]

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)

[@christianjt7018]

this solution works, I did it like that but Greg's solution is faster

[@noextrasugar]

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😊

[@azharuddinkhan1865]

Nice

[@philipbrujic4728]

Appreciate the video brother

[@ashwanigaur1828]

Awesome explanation

[@christinjose2504]

Thanks. Will the space complexity be O(logn) - height of the tree?

[@GregHogg]

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.

[@christinjose2504]

@@GregHogg good call!