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

🚀 neetcode.io/ - A better way to prepare for Coding Interviews
🐦 Twitter: / neetcode1
🥷 Discord: / discord
🐮 Support the channel: / neetcode
Coding Solutions: • Coding Interview Solut...
Problem Link: leetcode.com/problems/convert...
0:00 - Read the problem
1:40 - Drawing Explanation
6:32 - Coding Explanation
leetcode 108
This question was identified as an interview question from here: github.com/xizhengszhang/Leet...
#sorted #array #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

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

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

[@xjlonelystar]

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

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

[@arturkabitcher]

That's the best channel for leetcode prep. I know you must be busy with your Google job but keep posting videos - I think you can monetize it even better than any FAANG career

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

[@markomekjavic]

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

[@NeetCode]

Glad it was helpful!

[@DoJoStan]

Amazing explanation.

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

[@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)?

[@jayjagtap7873]

This solution is genious

[@shooby117]

Great explanations mate! :D

[@NeetCode]

Thanks!

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

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

[@asmahamdym]

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

[@zooomba62]

thank u fro the great explanation

[@sneezygibz6403]

Thanks man

[@geofox9484]

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

[@sushrutasengupta1273]

Can it be solved using two while loops seperately??

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

[@tabmax22]

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

[@roshangeorge97]

have you got in?

[@foudilbenouci482]

thank you

[@khoaanh7375]

So elegant

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

[@edwardteach2]

U a God

[@CST1992]

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

[@jobsearch9934]

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

[@Maattttheww]

Yep, I think that's a mistake.

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

[@shalsteven]

How about the time and space complexity?

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

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

[@inteligence317]

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

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

[@MaxFung]

spent 30 minutes on this and this tree STUMPED me

[@sakshisinha8213]

beauty

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

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

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

[@cathyhuang8557]

Second

[@nanobyte8425]

First

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

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