Validate Binary Search Tree - Depth First Search - Leetcode 98

🚀 neetcode.io/ - A better way to prepare for Coding Interviews
🐦 Twitter: / neetcode1
🥷 Discord: / discord
🐮 Support the channel: / neetcode
Coding Solutions: • Coding Interview Solut...
Problem Link: neetcode.io/problems/valid-bi...
0:00 - Read the problem
1:20 - Drawing solution
6:45 - Coding solution
leetcode 98
This question was identified as an amazon interview question from here: github.com/xizhengszhang/Leet...
#bst #python

[@NeetCode]

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

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

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

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

[@user-wy5es3xx2t]

@@NeetCode hey how do u do it in c++,my problem is what should i replace inplace of inifinity??

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

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

[@around_the_kyushu557]

These solutions are so efficient and elegant, thank you so much. I feel like I could never get to these solutions on my own.

[@AwesomeCadecraft]

I love how you present the problems so well, I figured it out at 3:23

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

[@julesrules1]

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

[@adambarbour4203]

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

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

[@solodolo42]

Nice one! for readability, I also re-wrote line 13 as[ if not (left < node.val< right): ] . Thanks

[@amritpatel6331]

You have explained so nicely. Thank you so much.

[@penguin1234ification]

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

[@ladydimitrescu1155]

coming back to this video after a month, best explanation out there!

[@kevinsu9347]

I really like your explanation, thanks dude

[@symbol767]

Thanks for your explanation!

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

[@silambarasan.ssethu9367]

Great explaination.Thanks dude

[@dithrox]

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

[@NeetCode]

Thanks, glad they are helpful!

[@hickasso]

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

[@hamoodhabibi7026]

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

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

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

[@theysay6696]

It makes so much sense now!

[@IK-xk7ex]

Awesome, explanation is as simple as it

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

[@mashab9129]

very clear explanation as always. thank you!

[@sachins6196]

Beautifully done

[@prashanthshetty8337]

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

[@rahuldey1182]

This guy is the Mozart of Leetcode.

[@sarthakjain1824]

best explanation there can be for this question

[@mariammeky3444]

helped me a lot thank you

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

[@alibaba888]

the explanation made my day...

[@iamburntout]

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

[@BTECESaumyaPande]

You are the best 👏👏

[@icvetz]

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

[@NeetCode]

Sure, I use Paint3D

[@hassanforever11]

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

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

[@wonheejang5594]

Wow, It's so much cleaner and understandable than leetcode solution. Thanks for the video. It helps a lot!!

[@netraamrale3850]

Superb...!!!

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

[@tongwang9464]

beautiful solution

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

[@Code4You1]

Very smart way

[@kailynn2449]

thanks so much

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

[@sanooosai]

thank you sir

[@tuananhao2057]

thank you for explaining, you are absolutely good man

[@tinymurky7329]

Wow, Big brain!

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

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

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

[@kirillzlobin7135]

You are amazing

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

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

[@billcosta]

you're genius

[@giridharsshenoy]

good solution

[@yaseeneltahir]

Big like!

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

[@fitnessking5446]

thanks a ton for the great explanation

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

[@ashleyspianoprogress1341]

I got this question in an interview.

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

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

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

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

[@pekarna]

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

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

[@khoango9241]

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

[@3ombieautopilot]

Did it using generators and inorder traversal.

[@Cruzylife]

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

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

[@VARUNSHARMA-shanks]

What is the problem with doing inorder traversal then check if it is sorted ?

[@sujithkumar1997]

extra memory for list and time to check if list is sorted

[@jvarunbharathi9013]

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

[@javatutorials6747]

Using inorder traversal can also a solution sir

[@musaalsathmangazi6415]

Can someone explain why we need to check the boundaries with inf, -inf?

[@saisurisetti6278]

How behind are you? Me: "Aight lets do this. Brute Force first.. wait how do we brute force?"

[@shaked1233]

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

[@placementbaadshah8604]

kzbin.info/www/bejne/goO7pGCrg62Jj7M

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

[@akankshasharma7498]

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

[@blitzspirit]

Reminder: please add complexity analysis.

[@ax5344]

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

[@lajoskicsi6910]

Same for me, did you find anything out since then?

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

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

[@moeheinaung235]

what's the time and space complexity?

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

[@pfiter6062]

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

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

[@user-mp5ri8ep4k]

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

[@thevagabond85yt]

can u give stack solution?

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

[@abhicasm9237]

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?

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

[@palishloko]

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.

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

[@KM-zd6dq]

Nice solution, but what if we have a node that has a same value with the root?

[@Lambyyy]

A binary search tree has distinct values, no duplicates.

[@skp6114]

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