Convert Sorted Array to Binary Search Tree - Leetcode 108 - Python

[@NeetCode]

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

[@kairokabir9696]

instaBlaster...

[@ax5344]

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!

[@chuckle_pugz96]

what are you doing now? Just curious cause I recently started coding.

[@roshangeorge97]

Yeah the only explanation i needed for like an hour.

[@moulee007]

​@@chuckle_pugz96will ask the same question to you after 2 years

[@sagivalia5041]

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

[@niko-l-]

2AM and I'm here. Man, you’re the best in explanations. Keep it going

[@NeetCode]

Haha, 12am over here. Thanks for the kind words!

[@wt7658]

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!

[@sf-spark129]

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)

[@souravchavan7730]

Thank you. Had a same doubt.

[@jointcc2]

Thanks. This has cleared my doubt.

[@ewanowacka4772]

I was thinking the same and implemented with m = (r+l)//2+1

[@alexandremarangonicosta]

Space complexity is actually O(n) too because you create a TreeNode for each elem of the array.

[@mmc64]

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.

[@balaganesh5484]

Time and memory complexity is O(n) my guess, we are traversing every input and we are creating node for every input.

[@jetunpatel-zw6tm]

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.

[@PorkBoy69]

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

[@xjlonelystar]

god, i appreciate you always explain even the most basic things. Absolutely amazing!

[@mohamedsalama2743]

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

[@ranjitasahu19]

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.

[@angelwidatti]

I do not understand one thing: if the tree is balanced BST, then why and how the space complexity would be O(log n)?

[@markomekjavic]

This is such a good explanation - thank you for also explaning how nested functions/methods work:)

[@NeetCode]

Glad it was helpful!

[@tanmaysontakke1813]

for c++ users u have to add extra step if left == right otherwise it will be an infinite loop

[@asmahamdym]

after watching your explanation I really can't understand from anyone else, Please make more videos

[@ruthylevi9804]

this is the video that made it click! thank you for explaining the reasoning in necessary detail behind all this :)

[@NeetCode]

Happy it was helpful!

[@tabmax22]

Dude if I get into Google I'm genuinely donating 10% of my first pay cheque to you

[@roshangeorge97]

have you got in?

[@jayjagtap7873]

This solution is genious

[@geofox9484]

Would this be wrong if I'm getting -10 and 5 as my 1st level after root?

[@CST1992]

Memory complexity is still O(n) as you're creating n nodes. How is it O(log n)?

[@danielsun716]

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

[@KyuriousBot]

How are we making sure at every step that the subtress are height balanced? Can someone please explain?

[@head0fmob]

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

[@sushrutasengupta1273]

Can it be solved using two while loops seperately??

[@DoJoStan]

Amazing explanation.

[@veliea5160]

in which case `l>r` "l" will be greater "r"

[@Pranav-nn1lu]

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.

[@veliea5160]

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

[@lucy2003-d8p]

thank u fro the great explanation

[@shooby117]

Great explanations mate! :D

[@NeetCode]

Thanks!

[@sneezygibz6403]

Thanks man

[@bharatapar3937]

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 ?

[@ligrt2426]

root.left = helper(l,m-1) change the 1 to l

[@jobsearch9934]

Wouldn't space complexity still be O(n) since were creating "n" nodes?

[@Maattttheww]

Yep, I think that's a mistake.

[@foudilbenouci482]

thank you

[@halahmilksheikh]

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

[@chaitanya_anand]

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

[@saitharun8114]

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

[@amberfatima2777]

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)

[@edwardteach2]

U a God

[@MaxFung]

spent 30 minutes on this and this tree STUMPED me

[@khoaanh7375]

So elegant

[@DmitriyKl]

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

[@nachiket9857]

I agree, it's more intuitive that way

[@aidanfarhi4582]

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.

[@Pushpraj_gour]

The simplest way of explaination this question if is ever existed then that guy has to watch this video to change his opinion

[@shalsteven]

How about the time and space complexity?

[@inteligence317]

In the pharmacy watching this lol I don't have anytime to do shit lol

[@sakshisinha8213]

beauty

[@justsomeguy8385]

I wasted so much time trying to come up with an iterative solution...

[@akagamishanks7991]

how is this problem easy lol

[@antoinenijhuis450]

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.

[@nanobyte8425]

First

[@cathyhuang8557]

Second

[@raunaqsingh875]

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; } };