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).
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
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?
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!
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.
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.
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!
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
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...
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
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.
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; } } } }
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.
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 :)
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)
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
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
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.
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;
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
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.
@@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!
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; } } };
the idea of the solution is still the same. you just need to terminate the loop with a break statement within the else case. then you can return the result outside the loop
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.
Hey can you say please which drawing tools you use there and which mic and recording software - Affiliate links would happily be clicked to support you! Thanks..
you could, but then you'd be reassigning root to the next node on each step of the loop. when you were done, root, one of your parameters, would no longer point to the original root of the tree. what if the code that called your function was relying on the root variable they passed to you? reassigning parameters is an anti-pattern except when the function explicitly makes clear that that is the intention (referred to as modifying in-place). also, since curr here is just a pointer/reference to the object and not a copy of the tree itself, it costs basically nothing to make that variable and preserve the original root parameter
May be the test case itself is wrong. Input doesn't make much sense as it isn't a valid BST, value 1 can't be to right side of value 3 as it was supposed to be a BST... for example a valid input BST would be something like [3,1,5,0,2,4,7, ...] , which would look like 3 1 5 0 2 4 7 : ? Hope that helps .
Hey @@rockstars369 Thanks for clarifying, yes this does make a lot of sense now. I was doing this for a Binary tree, which is valid in this case and might have some more cases to consider other than the approach mentioned in the video which is of BST.
![Lp. Сердце Вселенной #1 НАЧАЛО ПУТЕШЕСТВИЯ [Новый сезон] • Майнкрафт](http://i.ytimg.com/vi/380Q7gLWGvk/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
You are one really rare talented teacher!
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 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.
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
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!
This test case is failing in leetcode -
[3,5,1,6,2,0,8,null,null,7,4]
5
4
what to do bro
Only works on bst that guarantee to have p and q in it self not not normal binary tree
@@jakjun4077 Unless I'm misreading it, both 4 and 5 should both be in the left branch from the starting node of 3... Hmmmm....
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 : ...
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
I have become substantial better in coding and solving difficult problems thanks to your channel. Keep it up!
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
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?
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.
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.
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.
You are one of the best people who can explain programming problems.
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.
i honestly don't know what i would do without you, neetcode
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!
Man, your solutions always manage to impress me
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...
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 !
coincidence! exactly after one year of upload seeing this video.! Big respect for you.!
28/30 cases passed
Neet: "So I am gonna complete the solution in just 3 lines fellas"
Damn, I never knew this problem can be solved this way. Mind blown. Great approach. Thank you!
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
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.
Thank you so much! Please keep updating leetcode solutions! Your videos really help me a lot!! Great appreciate!
@NeetCode 4:59 I think the time complexity is O(n) because the BST isn’t necessarily balanced
Oh Wow interesting to see that not every tree question requires a recursion solution. Neat!
Recursive solution:
if (p.val = root.val) or ((p.val >= root.val and q.val
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;
}
}
}
}
Very neat solution and excellent explanation
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.
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
Amazing!! Thank you NeetCode
Thank you so much dude!!!
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)
there seem to be very little number of cases in the problem to realize, well done!
Thank you for the neat explanation. And the code as well.
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
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
Grateful to your work
Simple and effective solution !
@neetcode can u discuss tower of hanoi problem. I think it helps us to set a base for recursive problem.
Good explanation. Thanks.
Great video as always! Can you also solve lowest common ancestor of a binary tree please?
OMG! I'm so mad at myself I didn't see it.
What a brilliant solution
Wow great simple solution
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)
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
Wish you also solved the other (lowest common ancestor) binary tree problems. They are 4 of them.
thanks for the explanation of the question but now this question its medium not easy
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
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
Really helpful! Thank you!
Really awesome, thank you!
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
what if it's not a BST??
I tried just use root instead of cur, it still works.
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 didnt realize a binary search tree was sorted at first, and spent one hour trying to do bfs search lol
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
Love from Suman(IIT-Bhubaneshwar, odisha India
thank you sir
Thanks man, liked
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.
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
God like explanation!
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.
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!
just a suggestion can you make video on task scheduler problem too ?
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;
}
}
};
how is this medium but subtree of another tree easy? lol
very clever
Anyone know why my solution to this problem might be passing on LeetCode but failing on NeetCode?
THE GOAT
Is this still considered a DFS approach?
What software or app do you use to get these videos done? Like is that apple pencil on ipad? @neetcode
thank you
This solution no longer works guys. They changed up the ordering of the nodes
the idea of the solution is still the same. you just need to terminate the loop with a break statement within the else case. then you can return the result outside the loop
@@KiingDom does not work
@@manh9105 idk it worked for me
and here i was writing 5 different functions for no reason
I didnt even notice the fact that is was a BST and I solved it using recursion like a regular BT😂
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
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.
Hey can you say please which drawing tools you use there and which mic and recording software - Affiliate links would happily be clicked to support you! Thanks..
Sure, this is the mic I use: amzn.to/2RRrLQd
And I just use Paint3D for the drawings with a mouse.
Spent aprox. two hours trying to get a DFS or BFS implementation for this problem...and the answer is a few conditional loops, typical
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.
Bruh, neat! Or should I say neet!
why have we assigned a CURR value to the root, cant we use root directly in for loop?if any body know kindly drop your aws
you could, but then you'd be reassigning root to the next node on each step of the loop. when you were done, root, one of your parameters, would no longer point to the original root of the tree. what if the code that called your function was relying on the root variable they passed to you? reassigning parameters is an anti-pattern except when the function explicitly makes clear that that is the intention (referred to as modifying in-place). also, since curr here is just a pointer/reference to the object and not a copy of the tree itself, it costs basically nothing to make that variable and preserve the original root parameter
@@austin4855 thanks dude
@@austin4855 thanks dude
@@austin4855 okay seriously this guy is built different
This test case is failing in leetcode -
[3,5,1,6,2,0,8,null,null,7,4]
5
4
Anyone have any clue, why?
May be the test case itself is wrong. Input doesn't make much sense as it isn't a valid BST, value 1 can't be to right side of value 3 as it was supposed to be a BST... for example a valid input BST would be something like [3,1,5,0,2,4,7, ...] , which would look like
3
1 5
0 2 4 7
:
? Hope that helps .
Hey @@rockstars369
Thanks for clarifying, yes this does make a lot of sense now. I was doing this for a Binary tree, which is valid in this case and might have some more cases to consider other than the approach mentioned in the video which is of BST.