Binary Search Tree Iterator - Leetcode 173 - Python

0:00 - Read the problem
1:30 - Drawing Explanation
9:47 - Coding Explanation

leetcode 173

#meta #interview #python
Disclosure: Some of the links above may be affiliate links, from which I may earn a small commission.

[DavidDLee]

You CAN do it recursively in Python by writing a Generator function, which uses *yield* and *yield from.* The end result is a very clean in-order recursive traversal that's been consumed sequentially, but with O(h) memory ( O(1) for our own state + O(h) where Python keeps track of the generator state).

[manishk]

Me: The perfect intro doesn't exi-

NeetCode: Let's write some more NeetCode today

Me: (Throws earphones in the air) THERE IT IS !!!

[lucashowes]

Ik google prolly pays you a bag but they might be wasting your talents. Haven't had online instruction this quality since khan academy

[oeseven]

Is doing the inorder traversal and adding the root to a queue works too? it passes all cases on Leetcode and beats 70%. However, I just seen all the different answers and they all use a stack...nvm just seen more of the video. its too much space complexity.

[techno_season_]

Omg! Thank you so much! I love your videos Neetcode! Just curious, could you also solve Perfect Rectangles?

[techandmore]

Here did it little different:

class BSTIterator:

def __init__(self, root: Optional[TreeNode]):
self.root = root
self.stack = []
self.cur = root

def next(self) -> int:
while self.stack or self.cur:
while self.cur:
self.stack.append(self.cur)
self.cur = self.cur.left
self.cur = self.stack.pop()
result = self.cur.val
self.cur = self.cur.right
return result

def hasNext(self) -> bool:
return self.cur or self.stack

[ChanChan-pgwu]

You are always very helpful! I wish I could work with you in the future!

[alexandremarangonicosta]

Why space is O(h) if the first thing you do is to store the root, which contains all elements in its memory? Looks like space is also O(n).
EDIT: you are actually right....the left/right of a TreeNode, in python, only hold the reference of an object, not the object directly...so it behaves like a real pointer in C.

[usmanakram]

Does there exists a solution with O(1) space complexity for this problem?

[dewangpatil]

Hello Sir i am a big have a very important Could you please make solution playlist of Striver's SDE Sheet. Its will be very beneficial for us students

[harshavardhanveerannanaval]

Can someone please verify if it could be done this way?

class BSTIterator:

def __init__(self, root: Optional[TreeNode]):

arr=[]
def flatten(root):
if(root):
flatten(root.left)
arr.append(root.val)
flatten(root.right)

flatten(root)
self.arr=arr

def next(self) -> int:
return(self.arr.pop(0))

def hasNext(self) -> bool:
return(self.arr)

I just done a inorder traversal before hand and store it in an array

[kostaad]

I wonder if a yield based solutions with co-routines will be sufficient for an interviewer.

[xjlonelystar]

Man U doing more leetcode than me and u already have a job ☠️

[dusvn]

Ahaahahahah your first appoarch of solution is my solution and I know it's not efficient but I'm still stuct to find better solution.

[carloscarrillo]

You're a good man, NeetCode. Thanks!

[bhanuvarma]

In the given question they asked that implement in the ""In-order Traversal""...But you did it in the ""pre-Order""
##In-order traversal
1.left node
2.root node
3.right node
👉👉Please clear my doubt sir🙏🙏

[srx]

for some reason the constructor keeps going over my head

[ibrahimalshubaily]

Still dont get why does has next work?

[essamobeid]

amazing solution! thanks a lot for posting:)

[MysteriousIndiaYT]

Bro i am expert in python.
But very confused, which career i have to choose for my life.
Django Developer vs Data Scientist?
Can anyone please guide me.
I have little knowledge of both