Tree Question Playlist: kzbin.info/www/bejne/hZ-2n2WOerZng7s
@dishaagarwal15302 ай бұрын
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
@aditisharma24483 жыл бұрын
Looking at the the approach and the way you have explained it made my day. Absolutely beautiful and effortless.
@NeetCode3 жыл бұрын
Thanks, I'm happy it was helpful :)
@SritamNanda-x5h4 ай бұрын
@@NeetCode hey how do u do it in c++,my problem is what should i replace inplace of inifinity??
@tharunkumar5095Ай бұрын
@@SritamNanda-x5h If u still haven't figured it out Use long int For example, long left = LONG_INT
@jackarnold5713 жыл бұрын
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!
@NeetCode3 жыл бұрын
Thanks! I'm happy it was helpful
@talalnajam86922 жыл бұрын
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]
@joeltrunick94872 жыл бұрын
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
@gamerversez53722 жыл бұрын
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 🥲
@VasheshJ2 жыл бұрын
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
@anwarmohammad57952 жыл бұрын
this was a good one too..
@mehershrishtinigam54492 жыл бұрын
arey wah so smart bro. O(n) ez soln. very good
@julesrules12 жыл бұрын
Everything in this video is perfect. The logic, the way you explained it, the code, even the font! This made my day. Thanks!
@ranjeetkumaryadav39782 жыл бұрын
One other simple solution can be, do inorder traversal and compare current value with last visited value.
@jugsma66765 ай бұрын
exactly!
@PhanNghia-fk5rv4 ай бұрын
nice one bro
@surajpatil78954 ай бұрын
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
@minhvulai_yt3 ай бұрын
@@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
@of_mc91823 ай бұрын
@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.
@around_the_kyushu_2000 Жыл бұрын
These solutions are so efficient and elegant, thank you so much. I feel like I could never get to these solutions on my own.
@sugandhm26662 жыл бұрын
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)); } }
@reemmikulsky1382 Жыл бұрын
this bug is also relevant in cpp
@selfhelpguy55894 ай бұрын
Thank you so much!
@dineshkumarkb1372 Жыл бұрын
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!
@rushikeshkulkarni178422 күн бұрын
I exactly came at the point when i understood the failure point with same examples , great explanation :)
@solodolo429 ай бұрын
Nice one! for readability, I also re-wrote line 13 as[ if not (left < node.val< right): ] . Thanks
@AwesomeCadecraft Жыл бұрын
I love how you present the problems so well, I figured it out at 3:23
@penguin1234ification3 жыл бұрын
Thank you ! this is what I needed to click and understand.
@TheBeastDispenser Жыл бұрын
Thanks for this! I feel into the simple trap you mentioned at the beginning and was confused why I was failing some test cases.
@wonheeAlgorithm2 жыл бұрын
Wow, It's so much cleaner and understandable than leetcode solution. Thanks for the video. It helps a lot!!
@ladydimitrescu1155 Жыл бұрын
coming back to this video after a month, best explanation out there!
@rashaameen6116 ай бұрын
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
@tomonkysinatree2 ай бұрын
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
@rahuldey11822 жыл бұрын
This guy is the Mozart of Leetcode.
@aayushgupta69142 жыл бұрын
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.
@_nh_nguyen Жыл бұрын
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).
@natnaelberhane3141 Жыл бұрын
I was thinking exactly this. I think your way is more intuitive and easy to understand than what is shown in the video!
@jakjun4077 Жыл бұрын
@@_nh_nguyen can u explain why it is 2n for the solution since u only traverse all the node once why times two
@StfuSiriusly Жыл бұрын
@@_nh_nguyen constants mean nothing when talking about time complexity. 2n and n are equivilent unless you meant n^2
@piyusharyaprakash4365 Жыл бұрын
@@_nh_nguyen 2n reduces down to n so it's not that much big of a deal
@roni_castro Жыл бұрын
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.
@backflipinspace Жыл бұрын
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 Жыл бұрын
@@backflipinspace can you explain that a bit further? What do you mean by “in order”
@abyszero8620 Жыл бұрын
min/max would clash with standard library functions, so it's good practice not to name variables exactly the same.
@abyszero8620 Жыл бұрын
@@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.
@rajeshg35702 жыл бұрын
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..
@kevinsu93473 жыл бұрын
I really like your explanation, thanks dude
@iamburntout8 ай бұрын
the way you write code is art
@piyusharyaprakash4365 Жыл бұрын
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
@justinvilleneuve251 Жыл бұрын
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
@justinvilleneuve251 Жыл бұрын
this way you use O(1) space
@hoixthegreat8359Ай бұрын
@@justinvilleneuve251 You still use O(N), due to your recursive stack. But, depending on how you write your code, it may run slightly faster if you return immediately on finding an issue.
@niravarora98878 ай бұрын
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.
@tvrao1232 жыл бұрын
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
@hickasso2 жыл бұрын
Man, your channel is a divine beast. God, this is helping me so much, ty
@andrewpagan Жыл бұрын
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!
@amritpatel6331 Жыл бұрын
You have explained so nicely. Thank you so much.
@dithrox3 жыл бұрын
Thank you so much for these videos! Your solutions are crisp and easy to understand!
@NeetCode3 жыл бұрын
Thanks, glad they are helpful!
@edwardteach23 жыл бұрын
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
@NeetCode3 жыл бұрын
Thanks again 😄
@UsamaAziz-lb7kyАй бұрын
We can also do this by evaluating max and min value from a node. A node's value should always be greater than max value from all of its left nodes, and should be less than min value of all of its right nodes class Solution: def isValidBST(self, root: Optional[TreeNode]) -> bool: return self.isValid(root) def isValid(self, root): if not root: return True if not (root.val > self.getMaxValue(root.left) and root.val < self.getMinValue(root.right)): return False return self.isValid(root.left) and self.isValid(root.right) def getMaxValue(self, node): if not node: return float("-inf") return max(node.val, self.getMaxValue(node.left), self.getMaxValue(node.right)) def getMinValue(self, node): if not node: return float("inf") return min(node.val, self.getMinValue(node.left), self.getMinValue(node.right))
@blindview2006 Жыл бұрын
You can do inorder traversal without appending to array, just compare with the previous val when you're printing, instead of adding to array. This is same time and space
@hamoodhabibi70262 жыл бұрын
wow how do you come up with these solutions! leetcode master! mind blown every time
@deepakphadatare29492 жыл бұрын
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.
@haoli89832 ай бұрын
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.
@arunraj25272 жыл бұрын
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.
@mashab91292 жыл бұрын
very clear explanation as always. thank you!
@sarthakjain1824 Жыл бұрын
best explanation there can be for this question
@IK-xk7ex Жыл бұрын
Awesome, explanation is as simple as it
@jaymistry689 Жыл бұрын
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
@piyusharyaprakash4365 Жыл бұрын
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!
@adambarbour420310 ай бұрын
usually don't comment on videos but this is amzing. Just summed up about a week of lectures in 10 minutes
@Masterof_None Жыл бұрын
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
@backflipinspace Жыл бұрын
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.
@symbol7672 жыл бұрын
Thanks for your explanation!
@silambarasan.ssethu93672 жыл бұрын
Great explaination.Thanks dude
@prashanthshetty83373 жыл бұрын
Very neat! thank you so much for making these videos. This is helping me a lot.
@theysay66963 жыл бұрын
It makes so much sense now!
@mariammeky3444 Жыл бұрын
helped me a lot thank you
@prajjwaldubey5787 Жыл бұрын
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
@hassanforever113 жыл бұрын
Really nice explanation you made it look easy where as its seams complication at other resources thanks man
@alibaba8882 жыл бұрын
the explanation made my day...
@aadityakiran_s Жыл бұрын
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?
@alexkim896511 ай бұрын
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.
@pfiter6062 Жыл бұрын
I dont know why (root.val < left or root.val > right) gives me wrong answers
@bhaskyOld2 жыл бұрын
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?
@MagicMindAILabs2 жыл бұрын
// 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); }
@backflipinspace Жыл бұрын
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 }
@StfuSiriusly Жыл бұрын
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.
@jointcc2 Жыл бұрын
@@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.
@ashleyspianoprogress13418 ай бұрын
I got this question in an interview.
@jugsma66765 ай бұрын
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
@TheQuancy2 жыл бұрын
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
@Jack-mc7qe2 жыл бұрын
avg space complexity will be more in that case since in best case also u would be maintaining o(n) space
@jvarunbharathi9013 Жыл бұрын
What is the Space complexity of the Soution O(log(n)) worst case? log(n) being height of the tree
@Cruzylife Жыл бұрын
this is a sneaky question , passed 68 edge cases without considering the upper and lower bownd.
@danielsun7162 жыл бұрын
One quick question, 7:47, why we cannot set the base case like this if left < node.val < right: return True ?
@skp61142 жыл бұрын
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.
@danielsun7162 жыл бұрын
@@skp6114 Right!
@sachins61962 жыл бұрын
Beautifully done
@guynameddan4272 жыл бұрын
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?
@appcolab2 жыл бұрын
O(2N) for the both trees left and right but we drop the constant 2N to O(N)
@timhehmann2 жыл бұрын
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)
@3ombieautopilot5 ай бұрын
Did it using generators and inorder traversal.
@tuananhao20572 жыл бұрын
thank you for explaining, you are absolutely good man
@parthshah15632 жыл бұрын
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
@hoixthegreat8359Ай бұрын
O(n) space and O(n) time, so identical.
@sanooosai5 ай бұрын
thank you sir
@tongwang94642 жыл бұрын
beautiful solution
@pekarna2 жыл бұрын
Hi, I am lazy so I did it simply: Filled a list using in-order, and then just checked if it's sorted.
@tinymurky7329 Жыл бұрын
Wow, Big brain!
@billcosta11 ай бұрын
you're genius
@icvetz3 жыл бұрын
Hey NeetCode. May I ask what program you use for drawing your diagrams? Thanks!
@NeetCode3 жыл бұрын
Sure, I use Paint3D
@netraamrale3850 Жыл бұрын
Superb...!!!
@Code4You12 жыл бұрын
Very smart way
@VishnuVardhan-gr6op2 жыл бұрын
Please go through time and space complexity!
@BTECESaumyaPande2 жыл бұрын
You are the best 👏👏
@MagicMindAILabs2 жыл бұрын
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..
@austinkellum90972 жыл бұрын
I would like to know as well. I get why we would use DFS.
@khoango9241 Жыл бұрын
@5:37 Why is the upper bound 7? Is it supposed to be infinity?
@AbhishekBajpaiHereАй бұрын
why not just do in-order traversal and check if it is sorted ?
@shaked12332 жыл бұрын
Im wondering why the "if not" and not regular if, any reason behind it?
@placementbaadshah86042 жыл бұрын
kzbin.info/www/bejne/goO7pGCrg62Jj7M
@javatutorials674711 ай бұрын
Using inorder traversal can also a solution sir
@fitnessking54462 жыл бұрын
thanks a ton for the great explanation
@kaci02367 ай бұрын
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
@akankshasharma74982 жыл бұрын
should I try to come up with better solution if they are like, "Faster than 10%" ?
@rahuldass4522 жыл бұрын
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...
@shreyaskaup2 жыл бұрын
Yes 😊
@hickasso2 жыл бұрын
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
@kailynn24492 жыл бұрын
thanks so much
@ax53443 жыл бұрын
@ 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...)
@lajoskicsi69102 жыл бұрын
Same for me, did you find anything out since then?
@giridharsshenoy Жыл бұрын
good solution
@brianyehvg3 жыл бұрын
isnt traversing the tree with inorder traversal and putting it in an array and then going through the array also technically O(n)
@NeetCode3 жыл бұрын
Actually yes, i didn't think of that, but that is also a good solution.
@brianyehvg3 жыл бұрын
@@NeetCode i guess your solution is better anyways :) O(1) space vs O(n) space
@iambreddy2 жыл бұрын
@@brianyehvg Not really. You dont need to store the entire array. Just maintain the prev node and check if current node > prev.
@herono-4292 Жыл бұрын
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.
@sartipablo Жыл бұрын
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.
@jananisri62142 жыл бұрын
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.
@timhehmann2 жыл бұрын
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"))
@ssuriset3 ай бұрын
How behind are you? Me: "Aight lets do this. Brute Force first.. wait how do we brute force?"
@moeheinaung235 Жыл бұрын
what's the time and space complexity?
@blitzspirit11 ай бұрын
Reminder: please add complexity analysis.
@kirillzlobin7135 Жыл бұрын
You are amazing
@yaseeneltahir Жыл бұрын
Big like!
@ovaisahmedbinnajeeb1897 Жыл бұрын
A slightly better time solution. As soon as we reach the k value we break from the recursive loop: res=[] def dfs(node): if not node: return dfs(node.left) res.append(node.val) if len(res)==k: return dfs(node.right) dfs(root) return res[k-1]
@VARUNSHARMA-shanks3 жыл бұрын
What is the problem with doing inorder traversal then check if it is sorted ?
@sujithkumar19972 жыл бұрын
extra memory for list and time to check if list is sorted