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.
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.
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?
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.
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
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; } } } }
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!
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.
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
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)
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.
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?
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)
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.
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...
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
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) ?
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'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; }
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.
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 :)
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.
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 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.
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
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;
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.
@@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!
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?
![LOWEST COMMON ANCESTOR OF A BINARY TREE III [PYTHON]](http://i.ytimg.com/vi/vZxxksAP8yk/mqdefault.jpg)
🚀 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!
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
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.
I have become substantial better in coding and solving difficult problems thanks to your channel. Keep it up!
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?
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
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!
After seeing your solution, it didn't took me a minute to solve this problem in c++, Really very nice, keep going.
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?
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!
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.
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
Recursive approach came out with a little bit better space complexity but both 100% regarding TC. Great approach!
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!
You are one of the best people who can explain programming problems.
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;
}
}
}
}
Wow! I had overcomplicated the solution for this. Thanks.
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!
i honestly don't know what i would do without you, neetcode
It's amazing how simple and straightforward your solution is!
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.
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
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)
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
for the test case 1,2,3 the code is not working
coincidence! exactly after one year of upload seeing this video.! Big respect for you.!
Man, your solutions always manage to impress me
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.
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
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
@NeetCode 4:59 I think the time complexity is O(n) because the BST isn’t necessarily balanced
Damn, I never knew this problem can be solved this way. Mind blown. Great approach. Thank 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)
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.
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 !
Neet: "So I am gonna complete the solution in just 3 lines fellas"
Thank you so much! Please keep updating leetcode solutions! Your videos really help me a lot!! Great appreciate!
there seem to be very little number of cases in the problem to realize, well done!
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...
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) ?
Very neat solution and excellent explanation
OMG! I'm so mad at myself I didn't see it.
What a brilliant solution
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
Thank you for the neat explanation. And the code as well.
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
28/30 cases passed
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;
}
Amazing!! Thank you NeetCode
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.
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
Love from Suman(IIT-Bhubaneshwar, odisha India
Great video as always! Can you also solve lowest common ancestor of a binary tree please?
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
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.
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
Wish you also solved the other (lowest common ancestor) binary tree problems. They are 4 of them.
I tried just use root instead of cur, it still works.
Thank you so much dude!!!
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;
}
}
};
Simple and effective solution !
What software or app do you use to get these videos done? Like is that apple pencil on ipad? @neetcode
I didnt realize a binary search tree was sorted at first, and spent one hour trying to do bfs search lol
Wow great simple solution
beautiful solution
@neetcode can u discuss tower of hanoi problem. I think it helps us to set a base for recursive problem.
Grateful to your work
Should have mentioned straight away that p and q will exist and that p!=q like in the problem. Went too quickly over this one
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)
Good explanation. Thanks.
Thank you very much man
Would the space complexity also be O( log n)?
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.
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 no longer works for question 235
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
thanks for the explanation of the question but now this question its medium not easy
Really awesome, thank you!
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 considered a DFS approach?
what if it's not a BST??
Spent aprox. two hours trying to get a DFS or BFS implementation for this problem...and the answer is a few conditional loops, typical
thank you sir
just a suggestion can you make video on task scheduler problem too ?
Thanks man, liked
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.
how is this medium but subtree of another tree easy? lol
The problem was changed so it's a binary tree but not a binary search tree, so this solution no longer works.
That's a diff problem, the BST one still exists
God like explanation!
Really helpful! Thank you!
and here i was writing 5 different functions for no reason
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!
this being a medium and then finding a subtree being an easy makes me lose trust in the grading system lc has
Anyone know why my solution to this problem might be passing on LeetCode but failing on NeetCode?
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?