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

Показать описание

Please check my playlists for free DSA problem solutions:

My Favorite Courses:

Data Structures & Algorithms:

Python:

Web Dev / Full Stack:

Cloud Development:

Game Development:

SQL & Data Science:

Machine Learning & AI:

Рекомендации по теме

Комментарии

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

GregHogg

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

Dcebox

Bros actually the GOAT! explains things in a different way fr

amjadalthabteh

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#

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 + "\n");
}
if (node == null) {
return true;
}

if (node.val <= minVal || node.val >= maxVal) {
return false;
}

return IsValidBSTHelper(node.left, minVal, (long)node.val) && IsValidBSTHelper(node.right, (long)node.val, maxVal);
}
}

for the tree Greg
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😊

noextrasugar

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

christinjose

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

saurabhbhagat

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)

DanikDemchuk

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

Validate Binary Search Tree - Depth First Search - Leetcode 98

Validate Binary Search Tree - Leetcode 98

Validate Binary Search Tree - Leetcode 98

LeetCode 98. Validate Binary Search Tree (Algorithm Explained)

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

L46. Check if a tree is a BST or BT | Validate a BST

Validate Binary Search Tree - Leetcode 98

Validate Binary Search Tree

Validate Binary Search Tree (LeetCode 98) | Full solution with animations and visuals

Leetcode - Validate Binary Search Tree (Python)

Validate Binary Search Tree - LeetCode 98 - Python

Validate Binary Search Tree | Live Coding with Explanation | Leetcode - 98

FAANG BST QUESTION! | Validate Binary Search Tree - Leetcode 98

Validate Binary Search Tree | Leetcode 98

LeetCode Interview Problem | Validate Binary Search Tree

Validate Binary Search Tree Leetcode Recursion 3 line solution

Validate Binary Search Tree - LeetCode 98 - JavaScript

[Java] Leetcode 98. Validate Binary Search Tree [Binary Search Tree #3]

Validate Binary Search Tree - LeetCode 98 - Swift

Validate Binary Search Tree | Java | LeetCode - Medium - 98 | The Code Mate

Validate Binary Search Tree - LeetCode 98 - Coding Interview Questions

LeetCode 98. Validate Binary Search Tree - Interview Prep Ep 69

Leetcode 98. Validate Binary Search Tree (Python)

Validate Binary Search Tree - LeetCode #98 - Python, JavaScript, Java, C++