Validate Binary Search Tree - Depth First Search - Leetcode 98

[@NeetCode]

Tree Question Playlist: kzbin.info/www/bejne/hZ-2n2WOerZng7s

[@dishaagarwal1530]

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

[@rashaameen611]

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

[@talalnajam8692]

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]

[@joeltrunick9487]

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

[@gamerversez5372]

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 🥲

[@VasheshJ]

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

[@anwarmohammad5795]

this was a good one too..

[@mehershrishtinigam5449]

arey wah so smart bro. O(n) ez soln. very good

[@aditisharma2448]

Looking at the the approach and the way you have explained it made my day. Absolutely beautiful and effortless.

[@NeetCode]

Thanks, I'm happy it was helpful :)

[@SritamNanda-x5h]

@@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

[@sachinprabhuk6241]

@@SritamNanda-x5h Long datatype should do the trick.

[@jackarnold571]

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!

[@NeetCode]

Thanks! I'm happy it was helpful

[@sugandhm2666]

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

[@selfhelpguy5589]

Thank you so much!

[@draugno7]

they should've not given that test case...

[@julesrules1]

Everything in this video is perfect. The logic, the way you explained it, the code, even the font! This made my day. Thanks!

[@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!

[@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.

[@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))

[@ranjeetkumaryadav3978]

One other simple solution can be, do inorder traversal and compare current value with last visited value.

[@jugsma6676]

exactly!

[@PhanNghia-fk5rv]

nice one bro

[@surajpatil7895]

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_yt]

@@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_mc9182]

@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.

[@solodolo42]

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

[@rahuldey1182]

This guy is the Mozart of Leetcode.

[@tomonkysinatree]

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

[@edwardteach2]

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

[@NeetCode]

Thanks again 😄

[@niravarora9887]

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.

[@aayushgupta6914]

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

[@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.

[@tvrao123]

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

[@ahmedamr1124]

i used postorder and returned max and min for left and right node and if they are valid or not but your solution is much straight forward

[@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.

[@iamburntout]

the way you write code is art

[@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!

[@rajeshg3570]

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..

[@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

[@wonheeAlgorithm]

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!

[@penguin1234ification]

Thank you ! this is what I needed to click and understand.

[@rushikeshkulkarni1784]

I exactly came at the point when i understood the failure point with same examples , great explanation :)

[@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.

[@kevinsu9347]

I really like your explanation, thanks dude

[@hickasso]

Man, your channel is a divine beast. God, this is helping me so much, ty

[@haoli8983]

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.

[@hamoodhabibi7026]

wow how do you come up with these solutions! leetcode master! mind blown every time

[@deepakphadatare2949]

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.

[@jugsma6676]

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

[@IvanRadonjic-j9f]

My Solution, please let me know what you guys think: # 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): """ :type root: TreeNode :rtype: bool """ treeValues = [] def DFS_inOrder(current_node): if current_node.left is not None: DFS_inOrder(current_node.left) treeValues.append(current_node.val) if current_node.right is not None: DFS_inOrder(current_node.right) DFS_inOrder(root) #loop to check if it is sorted prev = treeValues[0] for i in range(1, len(treeValues)): if prev >= treeValues[i]: return False prev = treeValues[i] return True

[@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!

[@adambarbour4203]

usually don't comment on videos but this is amzing. Just summed up about a week of lectures in 10 minutes

[@TheQuancy]

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-mc7qe]

avg space complexity will be more in that case since in best case also u would be maintaining o(n) space

[@sarthakjain1824]

best explanation there can be for this question

[@arunraj2527]

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.

[@dithrox]

Thank you so much for these videos! Your solutions are crisp and easy to understand!

[@NeetCode]

Thanks, glad they are helpful!

[@reda-cf9gy]

guys i don't understand why [120,70,140,50,100,130,160,20,55,75,110,119,135,150,200] is a not a valid binary tree ?

[@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.

[@amritpatel6331]

You have explained so nicely. Thank you so much.

[@aidoskanapyanov3095]

For some reason breadth first search felt intuitive for me, here is the solution for those who are interested 👇 O(n) time and space: def isValidBST(self, root: Optional[TreeNode]) -> bool: if not root: return True min_val = None max_val = None q = deque([(root, min_val, max_val)]) while q: for _ in range(len(q)): node, min_val, max_val = q.popleft() if not node: continue if min_val is not None and node.val = max_val: return False q.append((node.left, min_val, node.val)) q.append((node.right, node.val, max_val)) return True

[@blitzspirit]

Reminder: please add complexity analysis.

[@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

[@Cruzylife]

this is a sneaky question , passed 68 edge cases without considering the upper and lower bownd.

[@mashab9129]

very clear explanation as always. thank you!

[@icvetz]

Hey NeetCode. May I ask what program you use for drawing your diagrams? Thanks!

[@NeetCode]

Sure, I use Paint3D

[@IK-xk7ex]

Awesome, explanation is as simple as it

[@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.

[@bhaskyOld]

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?

[@MagicMindAILabs]

// 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); }

[@kaci0236]

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

[@pekarna]

Hi, I am lazy so I did it simply: Filled a list using in-order, and then just checked if it's sorted.

[@alibaba888]

the explanation made my day...

[@parthshah1563]

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.

[@ashleyspianoprogress1341]

I got this question in an interview.

[@mariammeky3444]

helped me a lot thank you

[@symbol767]

Thanks for your explanation!

[@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?

[@alexkim8965]

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.

[@silambarasan.ssethu9367]

Great explaination.Thanks dude

[@MagicMindAILabs]

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..

[@austinkellum9097]

I would like to know as well. I get why we would use DFS.

[@theysay6696]

It makes so much sense now!

[@prashanthshetty8337]

Very neat! thank you so much for making these videos. This is helping me a lot.

[@tongwang9464]

beautiful solution

[@danielsun716]

One quick question, 7:47, why we cannot set the base case like this if left < node.val < right: return True ?

[@skp6114]

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.

[@danielsun716]

@@skp6114 Right!

[@guynameddan427]

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?

[@appcolab]

O(2N) for the both trees left and right but we drop the constant 2N to O(N)

[@timhehmann]

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)

[@VishnuVardhan-gr6op]

Please go through time and space complexity!

[@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]

[@rahuldass452]

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...

[@shreyaskaup]

Yes 😊

[@hickasso]

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

[@hassanforever11]

Really nice explanation you made it look easy where as its seams complication at other resources thanks man

[@sachins6196]

Beautifully done

[@h3ckphy246]

I solved it this way: checked if max value on the left side is less than current node and the min value on the right side is greater than the current node. But your solution seems cleaner. def isValidBST(self, root: Optional[TreeNode]) -> bool: minVal, maxVal = self.__validateBST(root) return not math.isinf(minVal) and not math.isinf(maxVal) def __validateBST(self, root: Optional[TreeNode]) -> tuple[Union[int, float], Union[int, float]]: if root is None: return (math.inf, -math.inf) minLeft, maxLeft = self.__validateBST(root.left) if maxLeft >= root.val: return (-math.inf, math.inf) minRight, maxRight = self.__validateBST(root.right) if minRight

[@jvarunbharathi9013]

What is the Space complexity of the Soution O(log(n)) worst case? log(n) being height of the tree

[@brianyehvg]

isnt traversing the tree with inorder traversal and putting it in an array and then going through the array also technically O(n)

[@NeetCode]

Actually yes, i didn't think of that, but that is also a good solution.

[@brianyehvg]

@@NeetCode i guess your solution is better anyways :) O(1) space vs O(n) space

[@iambreddy]

@@brianyehvg Not really. You dont need to store the entire array. Just maintain the prev node and check if current node > prev.

[@Code4You1]

Very smart way

[@3ombieautopilot]

Did it using generators and inorder traversal.

[@akankshasharma7498]

should I try to come up with better solution if they are like, "Faster than 10%" ?

[@billcosta]

you're genius

[@netraamrale3850]

Superb...!!!

[@pfiter6062]

I dont know why (root.val < left or root.val > right) gives me wrong answers

[@sanooosai]

thank you sir

[@BTECESaumyaPande]

You are the best 👏👏

[@giridharsshenoy]

good solution

[@javatutorials6747]

Using inorder traversal can also a solution sir

[@tuananhao2057]

thank you for explaining, you are absolutely good man

[@kailynn2449]

thanks so much

[@shaked1233]

Im wondering why the "if not" and not regular if, any reason behind it?

[@placementbaadshah8604]

kzbin.info/www/bejne/goO7pGCrg62Jj7M

[@tinymurky7329]

Wow, Big brain!

[@jananisri6214]

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.

[@timhehmann]

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"))

[@AbhishekBajpaiHere]

why not just do in-order traversal and check if it is sorted ?

[@kirillzlobin7135]

You are amazing

[@AR00STIKA]

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?

[@vinaydeep26]

we're comparing it with the boundaries

[@khoango9241]

@5:37 Why is the upper bound 7? Is it supposed to be infinity?

[@moeheinaung235]

what's the time and space complexity?

[@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.