Hi, just wanted to know that since condition is not for equal, wont test case with 2 nodes with same value fail say for this tree 23, left child is equal to root val not greater but this is not bst but running above code should not work on this case, let me know how this works
Dude, thank you so much for these videos! I struggled with understanding this (and many other) problem, even after looking at solutions in the discuss section. After watching this it makes perfect sense!
It will not work as he already shown the example for that. If root node right node is greater, that's good. But if root node right node's left node is smaller than root but greater than it's parent, then it will send true though answer is false
@@surajpatil7895 it will work since inorder traversal read your tree from left to right, meaning, if we have a tree like in the video, the result of inorder traversal would be [3, 5, 4, 7, 8]. Since 4 is greater than the prev number, return False
@surajpatil7895 You've misunderstood the example. What he showed was not an in-order traversal but simply checking the children of the current parent node.
great solution! My first intuition was to do an inorder traversal, and then do a one-pass to see if it's sorted. O(n). Downside is you have to loop through the entire tree even if the invalid node is the root's left child. class Solution: def isValidBST(self, root: Optional[TreeNode]) -> bool: res = [] self.inorder_traversal(root, res) return self.is_sorted(res)
Actually, I think this is a cleaner solution, as long as you use lazy evaluation. In Clojure, I think this is the way to go. (defn inorder [tree] (if (= nil tree) [] (concat (inorder (second tree)) (list (first tree)) (inorder (nth tree 2 nil))))) (apply
I think this approach is fine. If you keep on checking if the number appended to the stack (while doing an inorder traversal) is lesser than or equal to the number just before it, then you can return False. It also reduces space complexity bcoz u only need to store one number in the stack. Check out my solution: class Solution: def isValidBST(self, root: Optional[TreeNode]) -> bool: result = [] stack = [] while True: while root: stack.append(root) root = root.left if not stack: break node = stack.pop() if result: if result[0] >= node.val: return False result.pop() result.append(node.val) root = node.right
In java u need to pass left = Long.MIN_VALUE and right = Long.MAX_VALUE because there are test cases in which root value itself is Integer.MAX_VALUE and the if condition doesnt hit to return false. So having long as left and right boundaries make sure that node values(int type) lie within given range. Because longMIN < Integer < LongMax is always true class Solution { public boolean isValidBST(TreeNode root) { return helper(root, Long.MIN_VALUE, Long.MAX_VALUE); } private boolean helper(TreeNode node, long left, long right) { if(node==null) return true;
Wonderful. You read my mind. The first intuitive solution that came to my mind was to blindly compare the node values on the left and right with its immediate root node. I think its not only important to teach how to build an intuition but also to teach how not to build one. Thanks a ton for doing that. That's what has made your channel stand out. Keep it up!
Drawing out the solution was really good for this problem. I did the anticipated thing you pointed out at the beginning... then I tried to account for the issue when I realized what was wrong but couldn't frame the problem right. I think I am starting to jump into the code too soon. I need to be better about trying to break down the problem into smaller pieces first
My first intution was to follow inorder traversal and store it in the list, then validate if the list is sorted, I passed all the tests with it. Then I was trying to follow the approach you mentioned but figuring out left boundary and right boundary was actually very tricky, I am not sure if I could come up with that solution on my own.
great solution, if anyone is looking for Time and space complexity: Time: O(N) Space: O(N) This is because the DFS function is recursively called for each node in the BST, potentially leading to a call stack depth proportional to the number of nodes
Hey Neetcode, your algorithm takes O(n) time complexity and O(n) Space complexity (as you are traversing the tree recursively). Wouldn't it be much simpler if one were to take an inorder traversal and a single loop to check if the inorder traversal list is in acsending order or not. It would be of O(n) time and space complexity too.
Imo, the left and right range can be a bit confusing. Just do a simple inorder traversal, as a valid BST will always print a sorted series during inorder. So we just need to verify that and we're done.
@@noelcovarrubias7490"in-order" traversal is a specific variant of DFS on trees. For a valid BST, an in-order DFS traversal pattern is guaranteed to "visit" the nodes in globally increasing order.
My solution was to find the inorder traversal using dfs, store it in an array then just check if that array is sorted or not. The overall time complexity is O(N) also! it was easier to understand
same. You can just keep track of the last value visited in a variable "previous" instead of storing everything in an array. That way, you compare the current value with previous. If at any time current
Super helpful video! Question: based this BST definition, we assume every node has a unique value? I.e., if there are two nodes with equal values, then the tree is not a valid BST, correct? Something to clarify/disucss within an interview setting...
For each call of the function "valid" we have to make 2 comparisons (comparisons have O(1) time complexity) -> node.val < right -> node.val > left We touch each node only once (so we call the function "valid" N times in total), therefore it's O(2n) = O(n)
Just because the current node is true, it doesn't mean the children are true. We can't break out before calling the recursive function on the children. If false, we can break out since there is no point checking the children.
What if the root node or any other node inside is infinity or -infinity? Then this solution would break. If you put an equal's sign in addition to the comparators (=) then it will break if a tree is there with both left, right and its own value the same or if any value repeats in the BST. How did this solution pass that test case? Does it have something to do with it being written in Python?
Same question here. Does infinity considered smaller/bigger than any legal float value? Edit: I just did quick google search, and it is considered smaller/bigger than any legal number when comparing in Python. For Java, use Double.NEGATIVE_INFINITY & Double.POSITIVE_INFINITY, instead of Integer.MIN_VALUE & Integer.MAX_VALUE. I just confirmed the difference in LeetCode.
I think the naming of the parameters is just a bit confusing here. left means left bound (or lower bound) and right means right bound (or upper bound). So left and right doesn't refer to nodes, but the bounds. If we go to the left subtree then "node.val" becomes the new upper/right bound. If we go to the right subtree then "node.val" becomes the new lower/left bound. class Solution: def isValidBST(self, root: Optional[TreeNode]) -> bool: def valid(node, lowerBound, upperBound): if not node: return True if not (lowerBound < node.val and node.val < upperBound): return False; return valid(node.left, lowerBound, node.val) and valid(node.right, node.val, upperBound) return valid(root, float("-inf"), float("inf"))
U a God # Definition for a binary tree node. # class TreeNode(object): # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution(object): def isValidBST(self, root, low = float('-inf'), high = float('inf')): """ :type root: TreeNode :rtype: bool """ if not root: return True if not (low < root.val < high): return False left = self.isValidBST(root.left, low, root.val) right = self.isValidBST(root.right, root.val, high) return left and right
I have been practicing these questions for 2 months now but still I am not able to get the logic for most of the questions. Can someone from the comments help me?
I was asked this question as a follow up for a BST question in Google and I bombed it :(. It was easy but at that moment of time this did not cross my mind.
you dont really need to print and compare the entire sorted array. just maintain a variable "lastSeen" during your inorder traversal and keep checking if lastSeen < root.val....if yes then update the lastSeen; if not return false.
@ 8:43 , valid(node.left, left, node.val), if node.left is our current node, for me this is checking whether current node is between float"-inf" and node.parent. So current node should be smaller than its local parent. But the challenge @4:45 is 4 is smaller than its local parent, it is just bigger than the node two levels above. I got lost there. Any advice? (I know the code is right, but I just don't understand why...)
Great solution! I found the solution using INORDER traversal, but I'm not sure whether it is optimal or not. Can someone help me? def inorder(root, res): if not root: return inorder(root.left, res) res.append(root.val) inorder(root.right, res) res = [] inorder(root, res) for i in range(len(res)-1): if res[i] >= res[i+1]: return False return True
I didn't really get your brute force but my brute force was to just create BST into sorted array by inorder traversal and check if the array is sorted or not. BUT AS ALWAYS YOUR SOLUTION WAS VERY CLEAVER
That's not brute force I also came with the same solution using the inorder but the time complexity is O(N) but also taking O(N) space that's not brute force!
This solution may be tricky/difficult to implement in C++ ans there is no concept of +/- infinity. Also the range is given as INT_MIN to INT_MAX. Any comments?
Time complexity is O(n) Time | O(n) Space At that point, i'd rather just do the InorderTraversal, and check if the returned array is constantly increasing
This is a good solution but imo, a better and simpler way would be to just traverse the tree in "inorder". All BST's print out a sorted sequence when traversed in inorder. So all we really need to do is to check whether the last value we saw during our inorder traversal was smaller than my current node value; for which we can easily just maintain a global variable. That's it!! //Pseudocode: last = None def BST(Node root) { //base condition if(root == null){ return True } //left if(!BST(root.left)){ return False } //value comparision if(last == None){ last = root.val; }else{ if(last < root.val){ last = root.val }else{ return False } } //right if(!BST(root.right)){ return False } return True }
How is this simpler or better? The recursive solution is quite simple and elegant. Also you cant really say this is 'better' its just a different iterative way of solving it.
@@StfuSiriusly Well first of all, the iterative solution has the same time and space complexity as the recursive solution and if you happen to know anything about DFS inorder traversal you know it preserves order, so once you put all tree values in an array the rest is just checking whether the values in the array are in strictly increasing order. If you are in an interview this is the kind of solution that would come up to your mind instantly, which in a lot of times I think is better than coming up with a recursive case that may be error-prone. When I first tried this question I thought of both solutions, but I decided to go for the recursive solution and made the exact mistake Neetcode mentioned at the beginning of the video. This may be a good learning opportunity for myself but under interview condition it's always better to come up with solution having an easy and intuitive explanation while not compromising space and time complexity.
One simple method is to do inorder tree traversal: def isValidBST(self, root: Optional[TreeNode]) -> bool: res = [] def test(node, res): if not node: return True test(node.left, res) res.append(node.val) test(node.right, res) return res test(root, res) print(res) if len(res) != len(set(res)): return False return True if sorted(res) == list(res) else False
by brute force they usually mean the slower code and the optimized brut force is usually the faster code which it matters when you are dealing with very large data.
I could spend one year looking at this problem and I would never come up with infinity condition. I wonder if this a matter of practice and at some point it gets in to your intuition or you just have to be smart
@@Lambyyy not always.. when constructing a tree, we need to decide on one direction for equals to. For the leetcode solution, we need to just put in a check and return false. There is a test case that requires it.
Why you have used preorder traversal approach??? Any specific reason?? Inorder traversal also we can do 😅😅😅 What about post order traversal??? I see everywhere people make video with preorder only and don’t tell the reason behind this..
If you're comparing node.left with the previous left, and comparing node.right with previous right, aren't you just comparing the value against itself?
Tree Question Playlist: czcams.com/video/OnSn2XEQ4MY/video.html
Hi, just wanted to know that since condition is not for equal, wont test case with 2 nodes with same value fail say for this tree 23, left child is equal to root val not greater but this is not bst but running above code should not work on this case, let me know how this works
Looking at the the approach and the way you have explained it made my day. Absolutely beautiful and effortless.
Thanks, I'm happy it was helpful :)
@@NeetCode hey how do u do it in c++,my problem is what should i replace inplace of inifinity??
Dude, thank you so much for these videos! I struggled with understanding this (and many other) problem, even after looking at solutions in the discuss section. After watching this it makes perfect sense!
Thanks! I'm happy it was helpful
One other simple solution can be, do inorder traversal and compare current value with last visited value.
exactly!
nice one bro
It will not work as he already shown the example for that. If root node right node is greater, that's good. But if root node right node's left node is smaller than root but greater than it's parent, then it will send true though answer is false
@@surajpatil7895 it will work since inorder traversal read your tree from left to right, meaning, if we have a tree like in the video, the result of inorder traversal would be [3, 5, 4, 7, 8]. Since 4 is greater than the prev number, return False
@surajpatil7895 You've misunderstood the example. What he showed was not an in-order traversal but simply checking the children of the current parent node.
Everything in this video is perfect. The logic, the way you explained it, the code, even the font! This made my day. Thanks!
These solutions are so efficient and elegant, thank you so much. I feel like I could never get to these solutions on my own.
Thanks for this! I feel into the simple trap you mentioned at the beginning and was confused why I was failing some test cases.
I love how you present the problems so well, I figured it out at 3:23
usually don't comment on videos but this is amzing. Just summed up about a week of lectures in 10 minutes
great solution! My first intuition was to do an inorder traversal, and then do a one-pass to see if it's sorted. O(n). Downside is you have to loop through the entire tree even if the invalid node is the root's left child.
class Solution:
def isValidBST(self, root: Optional[TreeNode]) -> bool:
res = []
self.inorder_traversal(root, res)
return self.is_sorted(res)
def inorder_traversal(self, root, res):
if root:
self.inorder_traversal(root.left, res)
res.append(root.val)
self.inorder_traversal(root.right, res)
def is_sorted(self, arr):
if not arr:
return False
for i in range(1, len(arr)):
if arr[i]
Actually, I think this is a cleaner solution, as long as you use lazy evaluation. In Clojure, I think this is the way to go.
(defn inorder [tree]
(if
(= nil tree) []
(concat (inorder (second tree))
(list (first tree))
(inorder (nth tree 2 nil)))))
(apply
I had solved this question on leetcode in this way it went pretty well and when I tried on gfg , i got a wrong answer at a test case 🥲
I think this approach is fine. If you keep on checking if the number appended to the stack (while doing an inorder traversal) is lesser than or equal to the number just before it, then you can return False. It also reduces space complexity bcoz u only need to store one number in the stack.
Check out my solution:
class Solution:
def isValidBST(self, root: Optional[TreeNode]) -> bool:
result = []
stack = []
while True:
while root:
stack.append(root)
root = root.left
if not stack:
break
node = stack.pop()
if result:
if result[0] >= node.val:
return False
result.pop()
result.append(node.val)
root = node.right
return True
this was a good one too..
arey wah so smart bro. O(n) ez soln. very good
Nice one! for readability, I also re-wrote line 13 as[ if not (left < node.val< right): ] . Thanks
Thank you ! this is what I needed to click and understand.
In java u need to pass left = Long.MIN_VALUE and right = Long.MAX_VALUE because there are test cases in which root value itself is Integer.MAX_VALUE and the if condition doesnt hit to return false. So having long as left and right boundaries make sure that node values(int type) lie within given range.
Because longMIN < Integer < LongMax is always true
class Solution {
public boolean isValidBST(TreeNode root) {
return helper(root, Long.MIN_VALUE, Long.MAX_VALUE);
}
private boolean helper(TreeNode node, long left, long right) {
if(node==null)
return true;
if(!(node.valleft))
return false;
return (helper(node.left, left, node.val) && helper(node.right, node.val, right));
}
}
this bug is also relevant in cpp
Thank you so much!
Wonderful. You read my mind. The first intuitive solution that came to my mind was to blindly compare the node values on the left and right with its immediate root node. I think its not only important to teach how to build an intuition but also to teach how not to build one. Thanks a ton for doing that. That's what has made your channel stand out. Keep it up!
coming back to this video after a month, best explanation out there!
You have explained so nicely. Thank you so much.
I really like your explanation, thanks dude
wow how do you come up with these solutions! leetcode master! mind blown every time
I've been watching lot of solutions for this problem but i think this is the easiest and the best one.. simple superb.. thanks for this..
Great explaination.Thanks dude
Drawing out the solution was really good for this problem. I did the anticipated thing you pointed out at the beginning... then I tried to account for the issue when I realized what was wrong but couldn't frame the problem right. I think I am starting to jump into the code too soon. I need to be better about trying to break down the problem into smaller pieces first
Thanks for your explanation!
I wanna code like you .You make it sound so easy and simple.I really like your channel.If u ever in Newyork I wanna meet you.
Thank you so much for these videos! Your solutions are crisp and easy to understand!
Thanks, glad they are helpful!
Very neat! thank you so much for making these videos. This is helping me a lot.
very clear explanation as always. thank you!
Man, your channel is a divine beast. God, this is helping me so much, ty
Awesome, explanation is as simple as it
My first intution was to follow inorder traversal and store it in the list, then validate if the list is sorted, I passed all the tests with it. Then I was trying to follow the approach you mentioned but figuring out left boundary and right boundary was actually very tricky, I am not sure if I could come up with that solution on my own.
It makes so much sense now!
great solution, if anyone is looking for Time and space complexity:
Time: O(N)
Space: O(N) This is because the DFS function is recursively called for each node in the BST, potentially leading to a call stack depth proportional to the number of nodes
Hey NeetCode. May I ask what program you use for drawing your diagrams?
Thanks!
Sure, I use Paint3D
Wow, It's so much cleaner and understandable than leetcode solution. Thanks for the video. It helps a lot!!
best explanation there can be for this question
the way you write code is art
I remember looking at this problem 2 years ago and just being stumped. You made it so easy to understand in less than 10 minutes. Thank you so much!
Hey Neetcode, your algorithm takes O(n) time complexity and O(n) Space complexity (as you are traversing the tree recursively). Wouldn't it be much simpler if one were to take an inorder traversal and a single loop to check if the inorder traversal list is in acsending order or not. It would be of O(n) time and space complexity too.
Taking an inorder traversal and another loop actually takes 2n while NeetCode's algorithm takes n. Which means it is twice slower while both are O(n).
I was thinking exactly this. I think your way is more intuitive and easy to understand than what is shown in the video!
@@_nh_nguyen can u explain why it is 2n for the solution since u only traverse all the node once why times two
@@_nh_nguyen constants mean nothing when talking about time complexity. 2n and n are equivilent unless you meant n^2
@@_nh_nguyen 2n reduces down to n so it's not that much big of a deal
Beautifully done
I'd change left/right to min/max, so it's easier to understand and reduce confusion, as left reminds left node and so do right.
Imo, the left and right range can be a bit confusing. Just do a simple inorder traversal, as a valid BST will always print a sorted series during inorder. So we just need to verify that and we're done.
@@backflipinspace can you explain that a bit further? What do you mean by “in order”
min/max would clash with standard library functions, so it's good practice not to name variables exactly the same.
@@noelcovarrubias7490"in-order" traversal is a specific variant of DFS on trees. For a valid BST, an in-order DFS traversal pattern is guaranteed to "visit" the nodes in globally increasing order.
This guy is the Mozart of Leetcode.
Really nice explanation you made it look easy where as its seams complication at other resources thanks man
helped me a lot thank you
the explanation made my day...
Very simple logic is complicated
Max of left sub tree should be less than root and min of right sub tree should be greater than root
should I try to come up with better solution if they are like, "Faster than 10%" ?
My solution was to find the inorder traversal using dfs, store it in an array then just check if that array is sorted or not. The overall time complexity is O(N) also! it was easier to understand
same. You can just keep track of the last value visited in a variable "previous" instead of storing everything in an array. That way, you compare the current value with previous. If at any time current
this way you use O(1) space
Super helpful video! Question: based this BST definition, we assume every node has a unique value? I.e., if there are two nodes with equal values, then the tree is not a valid BST, correct? Something to clarify/disucss within an interview setting...
Yes 😊
Yes, if its equal we dont have a binary search, because we have to discard one side to make the search more efficienty. I think kkk
@5:37 Why is the upper bound 7? Is it supposed to be infinity?
Can someone explain why we need to check the boundaries with inf, -inf?
Thanks for the explanation. Had one question. @6:45 you said the time complexity is O(2n). I get why that's just O(n) but why 2n to begin with?
O(2N) for the both trees left and right but we drop the constant 2N to O(N)
For each call of the function "valid" we have to make 2 comparisons (comparisons have O(1) time complexity)
-> node.val < right
-> node.val > left
We touch each node only once (so we call the function "valid" N times in total), therefore it's O(2n) = O(n)
One quick question, 7:47, why we cannot set the base case like this
if left < node.val < right:
return True
?
Just because the current node is true, it doesn't mean the children are true. We can't break out before calling the recursive function on the children. If false, we can break out since there is no point checking the children.
@@skp6114 Right!
You are the best 👏👏
What is the Space complexity of the Soution O(log(n)) worst case? log(n) being height of the tree
What if the root node or any other node inside is infinity or -infinity? Then this solution would break. If you put an equal's sign in addition to the comparators (=) then it will break if a tree is there with both left, right and its own value the same or if any value repeats in the BST. How did this solution pass that test case? Does it have something to do with it being written in Python?
Same question here. Does infinity considered smaller/bigger than any legal float value?
Edit: I just did quick google search, and it is considered smaller/bigger than any legal number when comparing in Python.
For Java, use Double.NEGATIVE_INFINITY & Double.POSITIVE_INFINITY, instead of Integer.MIN_VALUE & Integer.MAX_VALUE. I just confirmed the difference in LeetCode.
Can someone explain this line - valid(node.right, node.val, right). I don't understand how node.val comes in the place of left node.
I think the naming of the parameters is just a bit confusing here. left means left bound (or lower bound) and right means right bound (or upper bound). So left and right doesn't refer to nodes, but the bounds.
If we go to the left subtree then "node.val" becomes the new upper/right bound.
If we go to the right subtree then "node.val" becomes the new lower/left bound.
class Solution:
def isValidBST(self, root: Optional[TreeNode]) -> bool:
def valid(node, lowerBound, upperBound):
if not node:
return True
if not (lowerBound < node.val and node.val < upperBound):
return False;
return valid(node.left, lowerBound, node.val) and valid(node.right, node.val, upperBound)
return valid(root, float("-inf"), float("inf"))
U a God
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution(object):
def isValidBST(self, root, low = float('-inf'), high = float('inf')):
"""
:type root: TreeNode
:rtype: bool
"""
if not root:
return True
if not (low < root.val < high):
return False
left = self.isValidBST(root.left, low, root.val)
right = self.isValidBST(root.right, root.val, high)
return left and right
Thanks again 😄
What is the problem with doing inorder traversal then check if it is sorted ?
extra memory for list and time to check if list is sorted
I have been practicing these questions for 2 months now
but still I am not able to get the logic for most of the questions. Can someone from the comments help me?
I dont know why (root.val < left or root.val > right) gives me wrong answers
I was asked this question as a follow up for a BST question in Google and I bombed it :(. It was easy but at that moment of time this did not cross my mind.
Im wondering why the "if not" and not regular if, any reason behind it?
czcams.com/video/LRXs-uNHVYQ/video.html
thank you for explaining, you are absolutely good man
i found some solution on leetcode solutions. it's short. but hard to know what's going on.
your solution is better than that to understand.
beautiful solution
i made a function for inorder traversal then return an array and compared with an sorted version of array but this way seems much easier
you dont really need to print and compare the entire sorted array. just maintain a variable "lastSeen" during your inorder traversal and keep checking if lastSeen < root.val....if yes then update the lastSeen; if not return false.
Superb...!!!
i have solved this by taking the in order traversal of the BST ,and if the traversal is strictly increasing then it is a BST otherwise not
Please go through time and space complexity!
Hi, I am lazy so I did it simply:
Filled a list using in-order, and then just checked if it's sorted.
what's the time and space complexity?
@ 8:43 , valid(node.left, left, node.val), if node.left is our current node, for me this is checking whether current node is between float"-inf" and node.parent. So current node should be smaller than its local parent. But the challenge @4:45 is 4 is smaller than its local parent, it is just bigger than the node two levels above. I got lost there. Any advice? (I know the code is right, but I just don't understand why...)
Same for me, did you find anything out since then?
Great solution!
I found the solution using INORDER traversal, but I'm not sure whether it is optimal or not. Can someone help me?
def inorder(root, res):
if not root:
return
inorder(root.left, res)
res.append(root.val)
inorder(root.right, res)
res = []
inorder(root, res)
for i in range(len(res)-1):
if res[i] >= res[i+1]: return False
return True
I got this question in an interview.
I didn't really get your brute force but my brute force was to just create BST into sorted array by inorder traversal and check if the array is sorted or not. BUT AS ALWAYS YOUR SOLUTION WAS VERY CLEAVER
That's not brute force I also came with the same solution using the inorder but the time complexity is O(N) but also taking O(N) space that's not brute force!
Very smart way
This solution may be tricky/difficult to implement in C++ ans there is no concept of +/- infinity. Also the range is given as INT_MIN to INT_MAX. Any comments?
// Recursive, In-Order validation
// MIN/MAX not required
TreeNode *prevv = NULL;
bool helperIsValidBSTInorder(TreeNode *root, TreeNode *prevv)
{
if(root == NULL)
{
return true;
}
// In - Order business place where you do something
// below conditions can be combined
if(!helperIsValidBSTInorder(root->left, prevv*))
{
return false;
}
if(prevv != NULL && root->val val)
{
return false;
}
prevv = root;
return helperIsValidBSTInorder(root->right/*, prevv);
}
this is a sneaky question , passed 68 edge cases without considering the upper and lower bownd.
Time complexity is O(n) Time | O(n) Space
At that point, i'd rather just do the InorderTraversal, and check if the returned array is constantly increasing
avg space complexity will be more in that case since in best case also u would be maintaining o(n) space
thanks a ton for the great explanation
thank you sir
thanks so much
This is a good solution but imo, a better and simpler way would be to just traverse the tree in "inorder". All BST's print out a sorted sequence when traversed in inorder. So all we really need to do is to check whether the last value we saw during our inorder traversal was smaller than my current node value; for which we can easily just maintain a global variable. That's it!!
//Pseudocode:
last = None
def BST(Node root) {
//base condition
if(root == null){
return True
}
//left
if(!BST(root.left)){
return False
}
//value comparision
if(last == None){
last = root.val;
}else{
if(last < root.val){
last = root.val
}else{
return False
}
}
//right
if(!BST(root.right)){
return False
}
return True
}
How is this simpler or better? The recursive solution is quite simple and elegant. Also you cant really say this is 'better' its just a different iterative way of solving it.
@@StfuSiriusly Well first of all, the iterative solution has the same time and space complexity as the recursive solution and if you happen to know anything about DFS inorder traversal you know it preserves order, so once you put all tree values in an array the rest is just checking whether the values in the array are in strictly increasing order. If you are in an interview this is the kind of solution that would come up to your mind instantly, which in a lot of times I think is better than coming up with a recursive case that may be error-prone. When I first tried this question I thought of both solutions, but I decided to go for the recursive solution and made the exact mistake Neetcode mentioned at the beginning of the video. This may be a good learning opportunity for myself but under interview condition it's always better to come up with solution having an easy and intuitive explanation while not compromising space and time complexity.
Hi, I am new to python and when I write the exact same code I am getting error for the def isValidBST line. Does anyone else get the error?
post the entire code that you have written
Wow, Big brain!
Did it using generators and inorder traversal.
Using inorder traversal can also a solution sir
One simple method is to do inorder tree traversal:
def isValidBST(self, root: Optional[TreeNode]) -> bool:
res = []
def test(node, res):
if not node:
return True
test(node.left, res)
res.append(node.val)
test(node.right, res)
return res
test(root, res)
print(res)
if len(res) != len(set(res)):
return False
return True if sorted(res) == list(res) else False
what if root = INT_MAX doesn't it gives wa.
you're genius
I don't understand the difference between the brute force and the optimize brut force. In both case we iterate trough each node and made a comparison.
by brute force they usually mean the slower code and the optimized brut force is usually the faster code which it matters when you are dealing with very large data.
You are amazing
good solution
can u give stack solution?
isnt traversing the tree with inorder traversal and putting it in an array and then going through the array also technically O(n)
Actually yes, i didn't think of that, but that is also a good solution.
@@NeetCode i guess your solution is better anyways :) O(1) space vs O(n) space
@@brianyehvg Not really. You dont need to store the entire array. Just maintain the prev node and check if current node > prev.
Big like!
I could spend one year looking at this problem and I would never come up with infinity condition. I wonder if this a matter of practice and at some point it gets in to your intuition or you just have to be smart
Nice solution, but what if we have a node that has a same value with the root?
A binary search tree has distinct values, no duplicates.
@@Lambyyy not always.. when constructing a tree, we need to decide on one direction for equals to. For the leetcode solution, we need to just put in a check and return false. There is a test case that requires it.
Why you have used preorder traversal approach??? Any specific reason??
Inorder traversal also we can do 😅😅😅
What about post order traversal???
I see everywhere people make video with preorder only and don’t tell the reason behind this..
I would like to know as well. I get why we would use DFS.
why you have written all that return statement ? i haven't undrstood
Very simple logic is complicated
If you're comparing node.left with the previous left, and comparing node.right with previous right, aren't you just comparing the value against itself?
we're comparing it with the boundaries