You are the first teacher among what I've checked who actually explained why when left > right, we need to return null. Others just take it for granted or gloss it over! Base conditions and details are always the most challenging to beginners! Thank you!
It's really admirable how you are not taking it for granted and conclude the helper function explanation as a Binary Search technique and explain it fully
Your explanation is succinct and straight forward. When I tried this problem originally there was an extremely long and convoluted explanation about unique solutions etc... and different potential strategies. I spent days reading the article and trying to find anywhere else on the internet where someone uses the same terms they used to explain the problem but couldn't find it. Thanks for posting such a useful video.
Best explanation ever. I am new to coding and appreciate you explain from basics such as 'why the helper can access the nums' and 'call the function' etc. thanks very much!
This is such a good explanation but this solution will not convert the given array into BST of [0,-3,9,-10,null,5]. Not that it matters, but I was a bit confused at first because that was the BST I was expecting. Here is why: -> Pointer input given:(0, 4) m = (0+4) //2 = 2 root = TreeNode(nums[2]) = 0 -> r.left = helper(0, 2-1=1) Pointer input given:(0, 1) m = (0+1) //2 = 0 root = TreeNode(nums[0]) = -10 -> r.left = helper(0, 0-1=-1), base-case met (L > R), return None -> r.right = helper(0+1=1, 1) Pointer input given:(1, 1) m = (1+1) //2 = 1 root = TreeNode(nums[1]) = -3 -> r.left = helper(1, 1-1=0), base-case met (L > R), return None -> r.right = helper(1+1=2, 1), base-case met (L > R), return None ... The final BST will look like [0,-10,5,null,-3,null,9] Easy fix or update to give you BST of [0,-3,9,-10,null,5] is actually to use math.ceil() rather than integer division here. It forces to round up. math.ceil((left + right) / 2)
That is for the worst case where you know that the tree is not balanced and skewed. In that case you linearly traverse across all nodes, correct me if I am wrong.
@@jetunpatel-zw6tm It is worst case (which is exactly what O notation is) but it is also every single case. You cannot add a node with visiting it. So your understanding doesn't really make sense.
if you're confused why it doesn't matter to choose left or right when computing the mid for even numbers, it's because you can still build a binary search tree differently, so in case of -10, -3 will be on its right in that case and it will still work fine
thank you so much, when you go by the code iteration the tree is forming with -10, -3 comes in right but in video its the other way so I was really confused.
you divide the list/ sublist by 2 (choosing the mid) each time you go to next tree level, so it will be automatically balance as dividing anything by 2 will give equal left and right sublist
hi, I am getting the wrong output : [0,-3,5,null,null,-3,9,null,0,0,null,-3,null,-3,5,null,null,null,null,-3,null,null,0,-3] def sortedArrayToBST(self, nums: List[int]) -> Optional[TreeNode]: def helper(l,r): if l>r: return None m = (l+r)//2 root = TreeNode(nums[m]) root.left = helper(1,m-1) root.right = helper(m+1,r) return root return helper(0,len(nums)-1) let me know what wrong i m doing ?
at line 16 and 17, because we are continously reducing the search space we will eventually reach a point where we cannot reduce it further and that's when 'l' will be greater than 'r'. You can test it out yourself by dry running the code :) I would recommend you to learn about binary search to understand this better.
@@Pranav-nn1lu ty. i figured that out after. when we calculate the first node in the last root.left, l=m=0 and since we pass `helper(l,m-1)`, m-1=-1 so r will be less than l
Because you are choosing the middle element of array as the current node and the elements to the right and left as right and left subtree. Since you are dividing the array in two equal(or diff. by 1) halves therefore you get balanced tree
I tried without a helper function, recursing the given one. But got more processing time. I would appreciate it if you could help me understand why.? ( Note: I am new to DSA) def sortedArrayToBST(self, nums: List[int]) -> Optional[TreeNode]: l = 0 r = len(nums)-1 mid = (l+r)//2 if l > r: return None root = TreeNode(nums[mid]) root.left = self.sortedArrayToBST(nums[0:mid]) root.right = self.sortedArrayToBST(nums[mid+1:r+1]) return root
I think it would be slightly easier to understand this solution without the additional helper function. Basically, you take the middle element, set it as the root node value, and everything to the left of the middle element gets passed down recursively to the same function (and becomes the left subtree), and everything to the right of the middle element gets passed down recursively to the same function as well (and becomes the right subtree): def sortedArrayToBST(self, nums: List[int]) -> Optional[TreeNode]: # base case - nums is empty if not nums: return None midIdx = len(nums)//2 root = TreeNode(nums[midIdx]) # middle value becomes root node value root.left = self.sortedArrayToBST(nums[0:midIdx]) # left subtree is everything to the left of the middle root.right = self.sortedArrayToBST(nums[midIdx+1:len(nums)]) # right subtree is everything to the right of middle return root
This solution will create a copy of each subarray every time you recursively call self.sortedArrayToBST. It's a valid solution but uses more memory than the helper function approach.
I know right, like in my head there are so many edge cases. What happens if the subtrees are of size 1 or 2 etc? I get that his code takes care of all of that, but it is not easy to see that directly I'd say.
Tree Question Playlist: ua-cam.com/video/OnSn2XEQ4MY/v-deo.html
instaBlaster...
You are the first teacher among what I've checked who actually explained why when left > right, we need to return null. Others just take it for granted or gloss it over! Base conditions and details are always the most challenging to beginners! Thank you!
what are you doing now? Just curious cause I recently started coding.
Yeah the only explanation i needed for like an hour.
@@chuckle_pugz96will ask the same question to you after 2 years
2AM and I'm here. Man, you’re the best in explanations. Keep it going
Haha, 12am over here. Thanks for the kind words!
It's really admirable how you are not taking it for granted and conclude the helper function explanation as a Binary Search technique and explain it fully
Without the pointer shenanigans:
class Solution:
def sortedArrayToBST(self, nums: List[int]) -> Optional[TreeNode]:
if not nums:
return None
mid = len(nums)//2
node = TreeNode(nums[mid])
node.left = self.sortedArrayToBST(nums[0: mid])
node.right = self.sortedArrayToBST(nums[mid+1: len(nums)])
return node
Your explanation is succinct and straight forward. When I tried this problem originally there was an extremely long and convoluted explanation about unique solutions etc... and different potential strategies. I spent days reading the article and trying to find anywhere else on the internet where someone uses the same terms they used to explain the problem but couldn't find it. Thanks for posting such a useful video.
Best explanation ever. I am new to coding and appreciate you explain from basics such as 'why the helper can access the nums' and 'call the function' etc. thanks very much!
god, i appreciate you always explain even the most basic things. Absolutely amazing!
This is such a good explanation but this solution will not convert the given array into BST of [0,-3,9,-10,null,5]. Not that it matters, but I was a bit confused at first because that was the BST I was expecting. Here is why:
-> Pointer input given:(0, 4)
m = (0+4) //2 = 2
root = TreeNode(nums[2]) = 0
-> r.left = helper(0, 2-1=1)
Pointer input given:(0, 1)
m = (0+1) //2 = 0
root = TreeNode(nums[0]) = -10
-> r.left = helper(0, 0-1=-1), base-case met (L > R), return None
-> r.right = helper(0+1=1, 1)
Pointer input given:(1, 1)
m = (1+1) //2 = 1
root = TreeNode(nums[1]) = -3
-> r.left = helper(1, 1-1=0), base-case met (L > R), return None
-> r.right = helper(1+1=2, 1), base-case met (L > R), return None
...
The final BST will look like [0,-10,5,null,-3,null,9]
Easy fix or update to give you BST of [0,-3,9,-10,null,5] is actually to use math.ceil() rather than integer division here. It forces to round up.
math.ceil((left + right) / 2)
Thank you. Had a same doubt.
Thanks. This has cleared my doubt.
I was thinking the same and implemented with m = (r+l)//2+1
This is such a good explanation - thank you for also explaning how nested functions/methods work:)
Glad it was helpful!
Space complexity is actually O(n) too because you create a TreeNode for each elem of the array.
Time and memory complexity is O(n) my guess, we are traversing every input and we are creating node for every input.
That is for the worst case where you know that the tree is not balanced and skewed. In that case you linearly traverse across all nodes, correct me if I am wrong.
@@jetunpatel-zw6tm It is worst case (which is exactly what O notation is) but it is also every single case. You cannot add a node with visiting it. So your understanding doesn't really make sense.
this is the video that made it click! thank you for explaining the reasoning in necessary detail behind all this :)
Happy it was helpful!
I do not understand one thing: if the tree is balanced BST, then why and how the space complexity would be O(log n)?
if you're confused why it doesn't matter to choose left or right when computing the mid for even numbers, it's because you can still build a binary search tree differently, so in case of -10, -3 will be on its right in that case and it will still work fine
thank you so much, when you go by the code iteration the tree is forming with -10, -3 comes in right but in video its the other way so I was really confused.
after watching your explanation I really can't understand from anyone else, Please make more videos
Dude if I get into Google I'm genuinely donating 10% of my first pay cheque to you
have you got in?
This solution is genious
Amazing explanation.
Great explanations mate! :D
Thanks!
for c++ users u have to add extra step if left == right otherwise it will be an infinite loop
thank u fro the great explanation
Would this be wrong if I'm getting -10 and 5 as my 1st level after root?
Thanks man
if not nums:
return None
l, r = 0, len(nums) - 1
m = (l + r) // 2
root = TreeNode(nums[m])
root.left = self.sortedArrayToBST(nums[l: m])
root.right = self.sortedArrayToBST(nums[m + 1: r + 1])
return root
thank you
Memory complexity is still O(n) as you're creating n nodes. How is it O(log n)?
How are we making sure at every step that the subtress are height balanced? Can someone please explain?
you divide the list/ sublist by 2 (choosing the mid) each time you go to next tree level, so it will be automatically balance as dividing anything by 2 will give equal left and right sublist
Can it be solved using two while loops seperately??
U a God
So elegant
hi, I am getting the wrong output :
[0,-3,5,null,null,-3,9,null,0,0,null,-3,null,-3,5,null,null,null,null,-3,null,null,0,-3]
def sortedArrayToBST(self, nums: List[int]) -> Optional[TreeNode]:
def helper(l,r):
if l>r:
return None
m = (l+r)//2
root = TreeNode(nums[m])
root.left = helper(1,m-1)
root.right = helper(m+1,r)
return root
return helper(0,len(nums)-1)
let me know what wrong i m doing ?
root.left = helper(l,m-1) change the 1 to l
spent 30 minutes on this and this tree STUMPED me
in which case `l>r` "l" will be greater "r"
at line 16 and 17, because we are continously reducing the search space we will eventually reach a point where we cannot reduce it further and that's when 'l' will be greater than 'r'. You can test it out yourself by dry running the code :)
I would recommend you to learn about binary search to understand this better.
@@Pranav-nn1lu ty. i figured that out after. when we calculate the first node in the last root.left, l=m=0 and since we pass `helper(l,m-1)`, m-1=-1 so r will be less than l
How is this guaranteed to be balanced? I guess intuitively it makes sense because you're always halving but that doesn't feel like a satisfying answer
Because you are choosing the middle element of array as the current node and the elements to the right and left as right and left subtree. Since you are dividing the array in two equal(or diff. by 1) halves therefore you get balanced tree
In the pharmacy watching this lol I don't have anytime to do shit lol
The simplest way of explaination this question if is ever existed then that guy has to watch this video to change his opinion
I tried without a helper function, recursing the given one. But got more processing time. I would appreciate it if you could help me understand why.? ( Note: I am new to DSA)
def sortedArrayToBST(self, nums: List[int]) -> Optional[TreeNode]:
l = 0
r = len(nums)-1
mid = (l+r)//2
if l > r:
return None
root = TreeNode(nums[mid])
root.left = self.sortedArrayToBST(nums[0:mid])
root.right = self.sortedArrayToBST(nums[mid+1:r+1])
return root
i think its because youre sending a part of array as parameters,it increases both space and time complexity ( Note: I am also new to DSA)
How about the time and space complexity?
Wouldn't space complexity still be O(n) since were creating "n" nodes?
Yep, I think that's a mistake.
beauty
I think it would be slightly easier to understand this solution without the additional helper function. Basically, you take the middle element, set it as the root node value, and everything to the left of the middle element gets passed down recursively to the same function (and becomes the left subtree), and everything to the right of the middle element gets passed down recursively to the same function as well (and becomes the right subtree):
def sortedArrayToBST(self, nums: List[int]) -> Optional[TreeNode]:
# base case - nums is empty
if not nums:
return None
midIdx = len(nums)//2
root = TreeNode(nums[midIdx]) # middle value becomes root node value
root.left = self.sortedArrayToBST(nums[0:midIdx]) # left subtree is everything to the left of the middle
root.right = self.sortedArrayToBST(nums[midIdx+1:len(nums)]) # right subtree is everything to the right of middle
return root
I agree, it's more intuitive that way
This solution will create a copy of each subarray every time you recursively call self.sortedArrayToBST. It's a valid solution but uses more memory than the helper function approach.
I wasted so much time trying to come up with an iterative solution...
how is this problem easy lol
I know right, like in my head there are so many edge cases. What happens if the subtrees are of size 1 or 2 etc? I get that his code takes care of all of that, but it is not easy to see that directly I'd say.
Second
First
If in case someone wants a C++ code:
class Solution {
public:
//Leetcode question # 108
TreeNode* buildTree(vector &nums,int lb,int ub){
if(lb>ub) return 0;
int mid=(lb+ub)/2;
TreeNode*newNode=new TreeNode(nums[mid]);
newNode->left=buildTree(nums,lb,mid-1);
newNode->right=buildTree(nums,mid+1,ub);
return newNode;
}
TreeNode* sortedArrayToBST(vector& nums) {
int lb=0,ub=nums.size()-1;
int mid=(lb+ub)/2;
TreeNode*root=new TreeNode(nums[mid]);
root->left=buildTree(nums,lb,mid-1);
root->right=buildTree(nums,mid+1,ub);
return root;
}
};