Iterative & Recursive - Binary Tree Inorder Traversal - Leetcode 94 - Python

🚀 neetcode.io/ - A better way to prepare for Coding Interviews
🥷 Discord: / discord
🐦 Twitter: / neetcode1
🐮 Support the channel: / neetcode
⭐ BLIND-75 PLAYLIST: • Two Sum - Leetcode 1 -...
💡 DYNAMIC PROGRAMMING PLAYLIST: • House Robber - Leetco...
Problem Link: leetcode.com/problems/binary-...
0:00 - Read the problem
0:49 - Recursive Explanation
2:43 - Recursive Coding
4:40 - Iterative Explanation
11:48 - Iterative Coding
leetcode 94
This question was identified as an apple coding interview question from here: github.com/xizhengszhang/Leet...
#apple #interview #python
Disclosure: Some of the links above may be affiliate links, from which I may earn a small commission.

[@jabir5768]

Thank you father

[@gauravsharma3829]

Thanks for explaining so well! It was so clear that I understood in one go.

[@MaheshKumar-qq7ts]

I was searching for this explanation few hours back and here it is. You are doing a great job and I mean literally "great job".

[@MaheshKumar-qq7ts]

Also I was worried that since you got job now video would not be that frequent, Please prove us wrong.

[@thevinarokiarajl2149]

I am as noobish as they come and I first check for any neetcode vids for a problem I encounter in LC. Ur goated fr

[@muneebmohd]

You have literally every single question explained, jesus. Thank you man I love you!

[@ancai5498]

I think the core idea to grasp the iterative solution is to understand the recursive solution first,
Basically, when you do the dfs(node->left), it just keeps finding its leftmost node until it doesn't, then you'll have to pop the stack to 'visit' the node(in-order), then dfs(node->right), it's the time for its right node.
Hope it helps.

[@vdyb745]

I can't thank you enough for your videos !!!

[@richardmunyao4607]

Thanks so much! This helped a bunch!

[@Goodday-nm7zp]

this channel has helped me so much, thank you!

[@ganeshbirajdar4382]

Thanks, very helpful 👍

[@pawelkorsunskiy9660]

You are a great teacher!

[@amitp277]

great explanation thanks!

[@dreamphoenix]

This is fantastic, thank you.

[@akira_asahi]

Thank you for the video. I am grateful for your time and contribution. Kind regards, Akira.

[@andreytamelo1183]

Thanks!

[@quirkyquester]

best video brother! love this!

[@cewenchi]

Only moment that i realized the importance of the tree structure with a stack is preparing jobs interview ...

[@trbhlk]

You should add the call stack explanation to the recursion section in your DS & Algos course. This was insanely helpful to understand recursion and draw a connection to stacks. Thank you.

[@mr.mrs.gutierrez4975]

Why I need to define private function “inorder”? Why I cannot directly recur self.inordertraversal(root.left) and self.inorderyraversal(root.right)?

[@HiHi-xl9kn]

Glad to see i'm not the only one that always mistakenly append the node to res lol. Could you share what you use to write/draw? ipad? tablet? touch screen?

[@RelaxationVideos99]

Awesome Thanks!

[@bossmusa9075]

thank you after your explanation i can do it on my own, the description was afwul

[@LilJollyJoker]

Thank You!

[@trbhlk]

You should add the call stack explanation to your recursion section from the DS & Algos course. This was insanely helpful to understand recursion.

[@gunahawk6893]

dude best explanation

[@lingyuhu4623]

Hope to have your video of 145. Binary Tree Postorder Traversal

[@zooomba62]

heyyy brooo thanks alot❤

[@trenaesthetics2139]

Bro I love u thanks man

[@arjunhamdalah4139]

Do you have basic cs leetcode Playlist? Thanks

[@alexgolomb363]

Thank you.

[@Marcox385]

Totally off-topic but how you got so good at drawing instructions? Lately I've been giving tutoring and I took inspiration from you (yet again) and used paint 3d for online sessions, the thing is that I always take too long to write/draw stuff that doesn't even looks that good. So, is it just practice or you have a distinct device other than a mouse?

[@olalekansogunle]

@NeetCode I have this exact question. Please help if you are able to get to answering

[@rikpatel]

He has responded to this before in another video. He uses Paint 3D and mouse. I guess its just practice. You can alternatively use Drawing pad

[@halahmilksheikh]

@@rikpatel He uses a mouse??? That's crazy. He writes like he uses a stylus.

[@St0n3dCold]

just use a stylus

[@Marcox385]

@@St0n3dCold lmao yeah why I didn't thought that? Let me also convert my display into a touchscreen. Better yet, let me get an expensive graphic tablet for something that isn't my profession, that way I could use an stylus, or several, to enhance the tutoring experience

[@yogeshmishra1726]

Do we need to know about iterative method if we know recursive one

[@user-ok4fx3kl6f]

I guess instead of inner while Ioop, we could simply use if condition , am I right ?
def inorder(root):
curr, stack = root, []
res = []
while curr or stack:
if curr:
stack.append(curr)
curr = curr.left
else:
curr = stack.pop()
res.append(curr)
curr = curr.right
return res

[@firstacc5442]

can you please explain Morris Traversal algorithm, please.

[@masternobody1896]

Nice

[@anonymoussloth6687]

Please do shortest path visiting all nodes on leetcode. It's a hard problem.

[@tanyashankar9966]

May I know why only stack is considered hare ??

[@andreypopov6166]

easy :) easy to remember...

[@gregorybai363]

Any vlogs coming?

[@ziiiiiiiiiii7325]

can somebody help me out here:
def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
result = []
stack = []
cur = root
while cur or stack:
while cur:
stack.append(cur)

[@NaveenKumar-xq6ce]

Because a node is a object of class TreeNode. Makes sense to store in stack cause it stores other things like functions and stuff. But we need to store values in array

[@nitrozeus5458]

Yer a wizard, Harry

[@leetcode650]

why are we appending the node to stack instead of just appending the values.

[@numberonep5404]

I don't think the link you put in the description is the right one :p nice video btw

[@vdyb745]

True leads to 108 instead of 94

[@NeetCode]

fixed!

[@codemarshal655]

Did you know, you can do iterative in / pre / post order traversals using same code??
Checkout how I did it in just 20 lines, in my new video
czcams.com/video/6wxNc8gCj8E/video.html

[@kaikim8402]

Is it Okay if u are solving this problem for the first time and ended up looking at the solution like this?
I feel guilty seeing the solution that i will be looking for solution every time i encounter problems that i can't solve.
Any advice?

[@erinwolf1563]

I'm currently in the same shoes as u right now.. but based on my research I think it's okay.. don't feel guilty

[@antoinenijhuis450]

Where are you at in your programming/comp science journey? @@erinwolf1563 @kaikim8402

[@tsunningwah3471]

zhin

[@tsunningwah3471]

b

[@tsunningwah3471]

zhina

[@bufdud4]

This iterative solution is pretty unintuitive.

[@user-lz5mb5nj2r]

yea i solved this problem iteratively with a hint of stack usage and it took me almost 5 hours.... my self-esteem is low now lol

[@antoinenijhuis450]

Where are you at in your programming/comp science journey tho? @@user-lz5mb5nj2r

[@servantofthelord8147]

The iterative code is hard for me to wrap my head around, but I'll keep revisiting it. For anyone in the same boat, I found this code on GeeksforGeeks and it helped me to understand it even more:
cur = root
stack = []
res = []
while True:
if cur:
stack.append(cur)
cur = cur.left
elif stack:
cur = stack.pop()
res.append(cur.val)
cur = cur.right
else:
return res

[@Baraa_Sy_99]

Thanks man, that was really helpful 🌷

[@servantofthelord8147]

@@Baraa_Sy_99 Glad it helped you!