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

Показать описание

0:00 - Read the problem
1:40 - Drawing Explanation
6:32 - Coding Explanation

leetcode 108

#sorted #array #python

NeetCode

Рекомендации по теме

Комментарии

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!

ax

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

niko-l-

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

sagivalia

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)

sf-spark

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

xjlonelystar

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!

wt

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.

mmc

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

balaganesh

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

markomekjavic

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

mohamedsalama

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

tabmax

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

ruthylevi

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

angelwidatti

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

asmahamdym

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

alexandremarangonicosta

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

tanmaysontakke

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

geofox

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

danielsun

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

CST

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

KyuriousBot

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

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

Convert Sorted Array to Binary Search Tree (LeetCode 108. Algorithm Explained)

Convert sorted array to binary search tree

Convert Sorted Array to Binary Search Tree

[Java] Leetcode 108. Convert Sorted Array to Binary Search Tree [Binary Search Tree #1]

LeetCode 108. Convert Sorted Array to Binary Search Tree - Interview Prep Ep 71

LeetCode 108. Convert Sorted Array to Binary Search Tree

Convert Sorted Array to BST | Leetcode - 108 | Trees #14

LeetCode #108 - Convert Sorted Array to Binary Search Tree

108. Convert Sorted Array to Binary Search Tree

Convert Sorted Array To Binary Search Tree | Leetcode Python Solution | Python

Convert Sorted Array to Binary Search Tree | 🚀 August LeetCode 🚀 | C++ | 🔥 Daily Challenge 🔥...

Convert Sorted Array to Balanced Binary Search Tree

Build Balanced BST from Sorted Array | C++ Placement Course | Lecture 28.5

Разбор задачи Leetcode 108 Convert Sorted Array to Binary Search Tree

108. Convert Sorted Array to Binary Search Tree - Day 26/31 Leetcode July Challenge

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

Convert Sorted Array to Binary Search Tree | Array to BST | LeetCode 108

Interview Questions | Convert Sorted Array to Binary Search Tree | JavaScript | NodeJS | leetcode

LEETCODE 108 (JAVASCRIPT) | CONVERT SORTED ARRAY TO BINARY SEARCH TREE

Convert sorted array to binary search tree | LeetCode 108 | Easy

Convert Sorted Array to Binary Search Tree | Leetcode 108 | Live coding session

Leetcode # 108. Convert Sorted Array to Binary Search Tree (Python)

Coding Universe LeetCode 108. Convert Sorted Array to Binary Search Tree with JavaScript!