For anyone like me confused by him comparing the values of the nodes, a bst is organized so that child nodes on the left are less than the parent node, and child nodes on the right are greater than the parent node. This applies recursively for any node with children.
You have a talent for making me feel like I overcomplicate things. Thank you for this solution and all the videos you make, your talent at problem-solving and teaching is godly.
This is one of the questions that I stared for a long time but understood it immediately after half of the video. Thanks for the great explanation as always.
But isn't that the same as O(h) where h is n?? So technically O(h) is the more correct solution because in the case you mentioned where it's O(n) it's also O(h).
Dang that's such an easy solution. Here I was thinking I would find the paths to both p and q and see where the paths differed, but no. This is way better!
I came up with the "solution" where I was checking if the node's value was one of the 2 given nodes and if not, I would go either left or right until I would find the solution. Your explanation was so much better, and it makes total sense. I've been wanting to ask; how did you get good at this? Are there any books you would recommend?
Wow that was way easier than I was making it. I didn't think about A) doing it iteratively or B) simply returning root if you have to split directions like that. I guess I didn't fully understand the problem. Thank you!
Simple recursive method given the leetcode constraints, you could do this without declaring low/high/res but I include them for clarity low = min(p.val, q.val) high = max(p.val, q.val) res = root.val # LCA because going left subtree leaves out high, right subtree leaves out low if low = res: return root elif res > low and res > high: return self.lowestCommonAncestor(root.left, p, q) elif res < low and res < high: return self.lowestCommonAncestor(root.right, p, q)
This solution has totally threw me off after realizing that we can make use of the nature of a binary search tree. I need to take a closer look at binary trees structure next time
this is what i was looking for thanks!!😁 I simplified it further def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode': if p.valroot.val: return self.lowestCommonAncestor(root.right,p,q) return root
This question made my brain hurt a bit, so glad you were here to explain this for all of us! Just wanted to express my gratitude love the way you kind of do an overall explanation before you code.
Question: Assume the BST is example 1 and q=0,p=5. Can't I just write a helper function that returns the path to these values from the root ,in this case : q_path=[left,left] and p_path=[left,right,right] and then just check between the 2 paths what is the largest common prefix which will lead me from the root to the LCA, no? Wouldn't this work and also be O(logn) ?
Here is the Java equivalent for those who are wondering: class Solution { public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { TreeNode current = root; while(true) { if(p.val > current.val && q.val > current.val) { current = current.right; } if(p.val < current.val && q.val < current.val) { current = current.left; } else { return current; } } } }
I think a more intuitive solution is that you could record all the nodes when traversing from root to p in an array, and all the nodes to q in other array, then find the common node in these 2 arrays.
Hello. Loving all these videos and the neetcode website (even though I am learning very slowly). Just an update, this problem on Leetcode is being listed as a Medium now and not Easy anymore. Actually just saw the entire video and....what!? How did you....wow this one just blew my mind.
Here is the code, u can run with your offline python environment class TreeNode: def __init__(self, x): self.val = x self.left = None self.right = None class BinarySearchTreeNode: def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode': cur = root
while cur: if p.val > cur.val and q.val > cur.val: cur = cur.right elif p.val < cur.val and q.val < cur.val: cur = cur.left else: return cur # Helper function to build a BST from a list def buildBST(nums): if not nums: return None root = TreeNode(nums[0]) for num in nums[1:]: if num is not None: root = insert(root, num) return root # Helper function to insert a value into a BST def insert(root, val): if not root: return TreeNode(val)
if val < root.val: root.left = insert(root.left, val) else: root.right = insert(root.right, val)
Thanks for the explanation. However, I'm confused on how 6 isn't the LCA for 7 and 9 in the second example. I must be missing something in the definition of LCA, because 6 is lower than 8 and has both 7 and 9 as descendants...
So is there some sort of official binary tree definition I can find? Isn't there a few presuppositions that are being made that make this problem easier? For one why does: TreeNode.left
I made this massively more complicated for myself by ignoring the constraint that confirmed `p` and `q` will exist in the list. This becomes much more complicated if you're having to binary search for nodes, then traverse back up to find the first common ancestor of both.
can someone explain why the second if statement has to be an else if? i feel like, logically, it doesnt matter since we are going down the tree regardless. while root: if p.val < root.val and q.val < root.val: root = root.left if p.val > root.val and q.val > root.val: root = root.right else: return root
Yes it doesn't matter for the solution but regardless the compiler will evaluate the second "if" statement even if the first "if" statement is true. When we use "elseIf" the compiler will not evaluate any other condition if one of the condition is true
you said that the space complexity is O(1) but shouldn't it be O(h) where h = height of the tree? Because we are using the call stack for the recursive calls.
There is no call stack in the solution given, there is a pointer to the current node being held which is constantly updated. This approach is iterative. For a recursive solution, you are correct.
To your point this could easily be done recursively which is what I did as well: class Solution { public: TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) { if (p->val > root->val && q->val > root->val) { return lowestCommonAncestor(root->right, p, q); } else if (p->val < root->val && q->val < root->val) { return lowestCommonAncestor(root->left, p, q); } else { return root; } } };
I solved the problem. But, overcomplicated it way too much. I found the 2 nodes separately first. And, then compared their traversal paths. The last matching node is the LCA.
i'm shocked by how your code is very simple while i wrote this much code: TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) { TreeNode* head= root; //root equal to one of them if(root->val==p->val || root->val== q->val) return root; //p and q one at left and the other at right if(p->val < root->val && q->val > root->val || p->val > root->val && q->val < root->val) return root; //p,q both at right if(root->val < p->val && root->val < q->val) return lowestCommonAncestor(root->right, p, q); //p,q both at left if(root->val > p->val && root->val > q->val) return lowestCommonAncestor(root->left, p, q); return root; }
This solution is not working This is the below code I used following the video. But it does not pass all test cases. Please let me know if I missed something. var lowestCommonAncestor = function (root, p, q) { if (!root) return null; let curr = root; while (curr) { if (p.val < curr.val && q.val < curr.val) curr = curr.left; else if (p.val > curr.val && q.val > curr.val) curr = curr.right; else return curr; } };
I saw other comments say that this solution is for leetcode 235 instead of 236. The difference between 235 and 236 is that 235 is Binary Search Tree 236 is Binary Tree. Hope this could help :)
Damnit I solved this using DP and felt good until I saw your insanely short and intuitive solution. I basically created a path to each node, popped values off the longer path and compared to the top of the shorter path until the path lengths were equal. When they were I popped off each value and compared and as soon as they were equal I returned the node where it was equal.
I think you are misunderstanding something here. When root is 2 (firstroot.left) then 0< 2 but 5>2 so root will be returned i.e. 2. I don't understand how you see 0 being returned.
Hi , looks like this solution is not getting accepted for me, curr = root while curr: if p.val > curr.val and q.val > curr.val: curr = curr.right elif p.val < curr.val and q.val < curr.val: curr = curr.left else: return curr Thanks
same for me; does not pass in c++. First TC passes though. TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) { TreeNode *cur = root;
while (cur) { if (cur->left && p->val < root->val && q->val < root->val) { cur = cur->left; } else if (cur->right && p->val > root->val && q->val > root->val) { cur = cur->right; } else { return cur; } } return nullptr;
is this still valid? the leetcode 236 example doesnt seem to structure the trees in the way you describe with right descendants being greater than the root
I am not 100% as I couldn't understand what the self.res was, assuming it's just a variable to store the result. But, looks like his solution in github will work against any tree and not just BST. I could be wrong XD
Thanks @Neetcode!! A potential follow up is : what is p and q may not exist in the tree, how would you modify the code? Really appreciate if you could share your thoughts here.
Quick question. I am guessing this approach works because the constraints said p and q will exist in the BST. If we did not know whether it exists or not, we would proceed to look for them then try to find a connection (where both are true which is where they meet), correct?
@@NeetCode Sorry, I only have a little money, I really appreciated your work but the amount can't represent my thanks. As a video maker, I know making video is a time consuming process. Your video helps me a lot. If I can find a full time job, I will donate more. Thanks for you sharing, your videos are better than many paid courses that I had before!
It is nowhere mentioned that the tree is a BST. So how did we conclude that a node with a value greater than the parent will always be in the right subtree and less than the parent will be in the left subtree?
🚀 neetcode.io/ - I created a FREE site to make interview prep a lot easier, hope it helps! ❤
you're assuming the tree is a binary search tree, what about binary trees that are not search trees? and what about non binary trees?
IDK WHY YOU STARTED THIS CHANNEL BUT THIS IS A BLESSING FOR people like me. THANK YOU SO MUCH !
He is single handedly starting thousands of careers
This code simplicity is God-level !!
Dude, I went like, this is it??
Then, I realized that this was actually it.
For real bro 🤯🤯
You are one really rare talented teacher!
For anyone like me confused by him comparing the values of the nodes, a bst is organized so that child nodes on the left are less than the parent node, and child nodes on the right are greater than the parent node. This applies recursively for any node with children.
Was looking for this. Thanks!
Thank you! I was confused by that part.
You have a talent for making me feel like I overcomplicate things. Thank you for this solution and all the videos you make, your talent at problem-solving and teaching is godly.
This is one of the questions that I stared for a long time but understood it immediately after half of the video. Thanks for the great explanation as always.
Same
I have become substantial better in coding and solving difficult problems thanks to your channel. Keep it up!
Recursive approach came out with a little bit better space complexity but both 100% regarding TC. Great approach!
After an hour, I finally did a O(n) solution, and i check NeetCode's video: 6 mins
Me : ...
Amazing video, kindly remind this is for Leetcode 235 instead of 236. One is for binary tree (unsorted), the other is for binary search tree (sorted)
Lmao I was on 236 thinking why nothing works
Time Complexity will be O(n) in the worst possible case of tree being left skewed or right skewed.
Anyway as always awesome explanation bro.
I was also about to type that :)
Still O(h)
But isn't that the same as O(h) where h is n?? So technically O(h) is the more correct solution because in the case you mentioned where it's O(n) it's also O(h).
But isn't a Binary Search Tree non-skewed unless stated?
Reminds me of the lowest common multiple (LCM) from math. You stop when a number cannot divide all the remainders at the same time. Thank you bro!
Wow! I had overcomplicated the solution for this. Thanks.
My mind was blown after seeing your solution. Thanks my man!
ya, same here :P i was overthinking it and completely went over the fact that this was a BST even though it said so explicitly lool
Dang that's such an easy solution. Here I was thinking I would find the paths to both p and q and see where the paths differed, but no. This is way better!
very elegant solution! i did not think of the concept that if both aren't greater or lesser, then we found the ancestor. mind blown when i saw that!
I came up with the "solution" where I was checking if the node's value was one of the 2 given nodes and if not, I would go either left or right until I would find the solution. Your explanation was so much better, and it makes total sense. I've been wanting to ask; how did you get good at this? Are there any books you would recommend?
It's amazing how simple and straightforward your solution is!
Wow that was way easier than I was making it. I didn't think about A) doing it iteratively or B) simply returning root if you have to split directions like that. I guess I didn't fully understand the problem. Thank you!
After seeing your solution, it didn't took me a minute to solve this problem in c++, Really very nice, keep going.
Simple recursive method given the leetcode constraints, you could do this without declaring low/high/res but I include them for clarity
low = min(p.val, q.val)
high = max(p.val, q.val)
res = root.val
# LCA because going left subtree leaves out high, right subtree leaves out low
if low = res:
return root
elif res > low and res > high:
return self.lowestCommonAncestor(root.left, p, q)
elif res < low and res < high:
return self.lowestCommonAncestor(root.right, p, q)
You are one of the best people who can explain programming problems.
This solution has totally threw me off after realizing that we can make use of the nature of a binary search tree. I need to take a closer look at binary trees structure next time
def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
def dfs(root):
if p.val < root.val and q.val < root.val:
return dfs(root.left)
if p.val > root.val and q.val > root.val:
return dfs(root.right)
return root
return dfs(root)
this is what i was looking for thanks!!😁
I simplified it further
def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
if p.valroot.val:
return self.lowestCommonAncestor(root.right,p,q)
return root
This question made my brain hurt a bit, so glad you were here to explain this for all of us! Just wanted to express my gratitude love the way you kind of do an overall explanation before you code.
@NeetCode 4:59 I think the time complexity is O(n) because the BST isn’t necessarily balanced
Question: Assume the BST is example 1 and q=0,p=5.
Can't I just write a helper function that returns the path to these values from the root ,in this case : q_path=[left,left] and p_path=[left,right,right]
and then just check between the 2 paths what is the largest common prefix which will lead me from the root to the LCA, no? Wouldn't this work and also be O(logn) ?
i honestly don't know what i would do without you, neetcode
Damn, I never knew this problem can be solved this way. Mind blown. Great approach. Thank you!
Man, your solutions always manage to impress me
recursive solution:
class Solution:
def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:
if p.val < root.val and q.val < root.val:
return self.lowestCommonAncestor(root.left, p, q)
elif p.val > root.val and q.val > root.val:
return self.lowestCommonAncestor(root.right, p, q)
else:
return root
Recursive solution:
if (p.val = root.val) or ((p.val >= root.val and q.val
Recursive solution is more inefficient, it has a call track overhead of O(n) worst case ina. Skewed tree and O(h = log n) best case
Here is the Java equivalent for those who are wondering:
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
TreeNode current = root;
while(true) {
if(p.val > current.val && q.val > current.val) {
current = current.right;
}
if(p.val < current.val && q.val < current.val) {
current = current.left;
}
else {
return current;
}
}
}
}
I think a more intuitive solution is that you could record all the nodes when traversing from root to p in an array, and all the nodes to q in other array, then find the common node in these 2 arrays.
Hello. Loving all these videos and the neetcode website (even though I am learning very slowly). Just an update, this problem on Leetcode is being listed as a Medium now and not Easy anymore.
Actually just saw the entire video and....what!? How did you....wow this one just blew my mind.
coincidence! exactly after one year of upload seeing this video.! Big respect for you.!
Here is the code, u can run with your offline python environment
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
class BinarySearchTreeNode:
def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
cur = root
while cur:
if p.val > cur.val and q.val > cur.val:
cur = cur.right
elif p.val < cur.val and q.val < cur.val:
cur = cur.left
else:
return cur
# Helper function to build a BST from a list
def buildBST(nums):
if not nums:
return None
root = TreeNode(nums[0])
for num in nums[1:]:
if num is not None:
root = insert(root, num)
return root
# Helper function to insert a value into a BST
def insert(root, val):
if not root:
return TreeNode(val)
if val < root.val:
root.left = insert(root.left, val)
else:
root.right = insert(root.right, val)
return root
if __name__ == "__main__":
solution = BinarySearchTreeNode()
nums_1 = [6, 2, 8, 0, 4, 7, 9, None, None, 3, 5]
p_val_1, q_val_1 = 2, 8
root1 = buildBST(nums_1)
p1 = TreeNode(p_val_1)
q1 = TreeNode(q_val_1)
result1 = solution.lowestCommonAncestor(root1, p1, q1)
print(result1.val)
nums_2 = [6, 2, 8, 0, 4, 7, 9, None, None, 3, 5]
p_val_2, q_val_2 = 2, 4
root2 = buildBST(nums_2)
p2 = TreeNode(p_val_2)
q2 = TreeNode(q_val_2)
result2 = solution.lowestCommonAncestor(root2, p2, q2)
print(result2.val)
nums_3 = [2, 1]
p_val_3, q_val_3 = 2, 1
root3 = buildBST(nums_3)
p3 = TreeNode(p_val_3)
q3 = TreeNode(q_val_3)
result3 = solution.lowestCommonAncestor(root3, p3, q3)
print(result3.val)
Thanks for the explanation. However, I'm confused on how 6 isn't the LCA for 7 and 9 in the second example. I must be missing something in the definition of LCA, because 6 is lower than 8 and has both 7 and 9 as descendants...
it's not the 'lowest' value, but the lowest node on the tree. 8 is below 6 on the tree
@@leeroymlg4692 even i was confused thanks for the clarification !
Would the space complexity also be O( log n)?
Thank you so much! Please keep updating leetcode solutions! Your videos really help me a lot!! Great appreciate!
So is there some sort of official binary tree definition I can find? Isn't there a few presuppositions that are being made that make this problem easier? For one why does:
TreeNode.left
this is binary SEARCH tree. Loot at the definition of that tree
I made this massively more complicated for myself by ignoring the constraint that confirmed `p` and `q` will exist in the list.
This becomes much more complicated if you're having to binary search for nodes, then traverse back up to find the first common ancestor of both.
there seem to be very little number of cases in the problem to realize, well done!
Why I am getting wrong answer for this Input with code below:
[3,5,1,6,2,0,8,null,null,7,4]
5
4
Output : null
Expected : 5
---------------------------------------- Code ----------------------------------------------------
class Solution:
def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
cur = root
while cur:
if p.val > cur.val and q.val > cur.val:
cur = cur.right
elif p.val < cur.val and q.val < cur.val:
cur = cur.left
else:
return cur
Very neat solution and excellent explanation
Love from Suman(IIT-Bhubaneshwar, odisha India
beautiful solution
Thank you for the neat explanation. And the code as well.
I tried just use root instead of cur, it still works.
Is it possible to solve this prob using recursion?
if root.val < p.val and root.val < q.val:
return self.lowestCommonAncestor(root.right, p, q)
elif root.val > p.val and root.val > q.val:
return self.lowestCommonAncestor(root.left, p, q)
else:
return root
@@elgizabbasov1963 Would this then be O(N) space because of the call stack?
@@toni9595 yes worst case O(n) average O(log n)
Neet: "So I am gonna complete the solution in just 3 lines fellas"
for the test case 1,2,3 the code is not working
can someone explain why the second if statement has to be an else if? i feel like, logically, it doesnt matter since we are going down the tree regardless.
while root:
if p.val < root.val and q.val < root.val:
root = root.left
if p.val > root.val and q.val > root.val:
root = root.right
else:
return root
Yes it doesn't matter for the solution but regardless the compiler will evaluate the second "if" statement even if the first "if" statement is true. When we use "elseIf" the compiler will not evaluate any other condition if one of the condition is true
Simple and effective solution !
you said that the space complexity is O(1) but shouldn't it be O(h) where h = height of the tree? Because we are using the call stack for the recursive calls.
There is no call stack in the solution given, there is a pointer to the current node being held which is constantly updated. This approach is iterative. For a recursive solution, you are correct.
To your point this could easily be done recursively which is what I did as well:
class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if (p->val > root->val && q->val > root->val)
{
return lowestCommonAncestor(root->right, p, q);
}
else if (p->val < root->val && q->val < root->val)
{
return lowestCommonAncestor(root->left, p, q);
}
else
{
return root;
}
}
};
Amazing!! Thank you NeetCode
Wish you also solved the other (lowest common ancestor) binary tree problems. They are 4 of them.
28/30 cases passed
I solved the problem. But, overcomplicated it way too much. I found the 2 nodes separately first. And, then compared their traversal paths. The last matching node is the LCA.
Thanks NeetCode!
I think i wrote a little easier solution after watching your video explanation before watching coding part.
Could you plz share that for a poor soul here
i'm shocked by how your code is very simple while i wrote this much code:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
TreeNode* head= root;
//root equal to one of them
if(root->val==p->val || root->val== q->val)
return root;
//p and q one at left and the other at right
if(p->val < root->val && q->val > root->val || p->val > root->val && q->val < root->val)
return root;
//p,q both at right
if(root->val < p->val && root->val < q->val)
return lowestCommonAncestor(root->right, p, q);
//p,q both at left
if(root->val > p->val && root->val > q->val)
return lowestCommonAncestor(root->left, p, q);
return root;
}
Grateful to your work
Great video as always! Can you also solve lowest common ancestor of a binary tree please?
Good explanation. Thanks.
Wow great simple solution
OMG! I'm so mad at myself I didn't see it.
What a brilliant solution
using recursion wouldnt the space complexity be O(logn) since the callstack will at most have logn recursive calls at a time?
This is not recursion, it's just a loop.
You can also do
while(true) {
}
and the solution will still work as we are guaranteed to find p and q
This solution is not working
This is the below code I used following the video. But it does not pass all test cases. Please let me know if I missed something.
var lowestCommonAncestor = function (root, p, q) {
if (!root) return null;
let curr = root;
while (curr) {
if (p.val < curr.val && q.val < curr.val) curr = curr.left;
else if (p.val > curr.val && q.val > curr.val) curr = curr.right;
else return curr;
}
};
Everything seems fine. I tried your exact code in leetcode, it passed
I saw other comments say that this solution is for leetcode 235 instead of 236. The difference between 235 and 236 is that
235 is Binary Search Tree
236 is Binary Tree.
Hope this could help :)
@@cici-lx6np tnx i was scratching my head
thanks for the explanation of the question but now this question its medium not easy
Thank you very much man
Damnit I solved this using DP and felt good until I saw your insanely short and intuitive solution.
I basically created a path to each node, popped values off the longer path and compared to the top of the shorter path until the path lengths were equal. When they were I popped off each value and compared and as soon as they were equal I returned the node where it was equal.
Thank you so much dude!!!
@neetcode can u discuss tower of hanoi problem. I think it helps us to set a base for recursive problem.
Hi. By this algorithm, wouldn't a case where p = 0 and q = 5 return an answer of 0. Shouldn't the answer be 2 as 0 is not an ancestor of 5?
I think you are misunderstanding something here. When root is 2 (firstroot.left) then 0< 2 but 5>2 so root will be returned i.e. 2. I don't understand how you see 0 being returned.
Hi , looks like this solution is not getting accepted for me,
curr = root
while curr:
if p.val > curr.val and q.val > curr.val:
curr = curr.right
elif p.val < curr.val and q.val < curr.val:
curr = curr.left
else:
return curr
Thanks
Hi @radhika i think you are looking at 235 not 236.
Yeah it’s saying wrong answer for me too, but it passes the first test case
same for me; does not pass in c++. First TC passes though.
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
TreeNode *cur = root;
while (cur) {
if (cur->left && p->val < root->val && q->val < root->val) {
cur = cur->left;
} else if (cur->right && p->val > root->val && q->val > root->val) {
cur = cur->right;
} else {
return cur;
}
}
return nullptr;
}
Works for me in C#
Yeah, it didn't work for me too.
is this still valid? the leetcode 236 example doesnt seem to structure the trees in the way you describe with right descendants being greater than the root
it is a Binary Search Tree bro...
what if it's not a BST??
thank you sir
just a suggestion can you make video on task scheduler problem too ?
Really awesome, thank you!
God like explanation!
elegant solution, even without any recursion! why is the solution on your github more complex?
I am not 100% as I couldn't understand what the self.res was, assuming it's just a variable to store the result. But, looks like his solution in github will work against any tree and not just BST. I could be wrong XD
Is this still considered a DFS approach?
Thanks @Neetcode!! A potential follow up is : what is p and q may not exist in the tree, how would you modify the code? Really appreciate if you could share your thoughts here.
This no longer works for question 235
Quick question.
I am guessing this approach works because the constraints said p and q will exist in the BST. If we did not know whether it exists or not, we would proceed to look for them then try to find a connection (where both are true which is where they meet), correct?
Anyone know why my solution to this problem might be passing on LeetCode but failing on NeetCode?
What software or app do you use to get these videos done? Like is that apple pencil on ipad? @neetcode
Thanks man, liked
Spent aprox. two hours trying to get a DFS or BFS implementation for this problem...and the answer is a few conditional loops, typical
I didnt realize a binary search tree was sorted at first, and spent one hour trying to do bfs search lol
Really helpful! Thank you!
Thanks!
Hey Shanshan - thank you so much, I really appreciate it!! 😊
@@NeetCode Sorry, I only have a little money, I really appreciated your work but the amount can't represent my thanks. As a video maker, I know making video is a time consuming process. Your video helps me a lot. If I can find a full time job, I will donate more. Thanks for you sharing, your videos are better than many paid courses that I had before!
@@shanshanyu5954 Its the thought that counts!
It is nowhere mentioned that the tree is a BST. So how did we conclude that a node with a value greater than the parent will always be in the right subtree and less than the parent will be in the left subtree?
you are doing 236, this is 235
@@rethern7966 yeah I figured it out after sometime lol
are binary trees always like this? such that values on the left are lower and right are higher?
Yes your understanding is correct.
root value will be greater than left and less than right.
@@wfkpk No, this is not correct. Binary SEARCH Trees are always like this. A plain old Binary Tree has no such guarantee.
And even then, you should always try and be clear if the BST allows duplicates and how that shakes out for the left/right sorting.
thank you
THE GOAT
and here i was writing 5 different functions for no reason
very clever