L9. Iterative Preorder Traversal in Binary Tree | C++ | Java | Stack

[@takeUforward]

Please likeeee, shareeee and subscribeeeeeeee :) Also follow me at Insta: Striver_79

[@democratcobra]

Understood

[@sarthakbhatia7888]

done

[@AbhishekKumar-vr7sh]

Yesterday I gave my paytm interview and all the dsa questions asked were from the sde sheet. Moreover, the questions asked from the core subjects were from the core sheet. I was able to crack the interview with great ease all thanks to striver bhaiya OP. You are the best mentor in this world 🔥

[@AbhishekKumar-vr7sh]

@Himanshu Kataria 😂😂😂

[@debanjan_poddar]

You gave the interview yesterday.. How are you already sure that you will be selected?

[@AbhishekKumar-vr7sh]

@@debanjan_poddar It was an on campus interview. Results came out that night itself. Processing is faster in case of on campus placement.

[@AbhishekKumar-vr7sh]

@@aadeshsharma0001 thanks bro

[@singhsahab9478]

@Himanshu Kataria lol

[@111rhishishranjan2]

vector Solution::preorderTraversal(TreeNode* A) { stackst; TreeNode*node =A; vectorv; while(!st.empty() || node != NULL){ if(node != NULL){ v.push_back(node->val); st.push(node); node = node->left; } else{ node = st.top(); st.pop(); node = node->right; } } return v; } //this is a nice stack approach . with more clean code.

[@curs3m4rk]

watched a lot of videos for iterative traversal, but this one hit my brain in first attempt. Your explanation is great man

[@aryanpinto5105]

Was just able to code on my own. The way you give the intuition is just next level. Tysm Striver. Grateful to have a teacher like you.❤💯

[@piyushsaxena6243]

this is the best tree series till date , thanks a lot striver, would be really helpful if you could bring a playlist on dp on trees as well for both cp and interviews.

[@shivangisrivastava1158]

i am thrilled at my transformation, i was able to write correct code before looking at your code! Tysm bhaiya😵♥️

[@harshvardhanmishra1072]

Started this tree series today and I don't know when I come up to the Lecture number 9. Such a wonderful explanation. Thanks you so much Sir for doing so much effort for us.😊

[@Ishan301]

Striver is life saviour for tier-3 college guys like me. Thank you.

[@Codeology708]

This Man Is a great example for those who say you can get a placement in Giant MNC's . Thanks Bhaiya You inspired me a lot

[@abhishekanand6847]

What ,it means --- Vectorpreorder Traversal(Treenode* root )

[@user-vaidesh]

It means the function is returning a vector that contains data in the form of integers and the function takes a struct or class of node to represent a treee

[@thegreekgoat98]

What an explanation!!!!! I wrote the C++ code by myself after watching the explanation part...

[@vishalwaghmare3130]

This is the best channel I have come across on Data Structures/Coding. Thanks a lot!

[@vasudhajha9115]

Hello Striver! I hope you're doing well :) Thank you so much for making these series that newbies like me can come back to again and again. The passion that you bring to teaching is infectious and in a sea of tutorial hell, your tutorials are a guiding light and the best path to follow! Really appreciate the effort that you put to help countless people. Your work is inspiring.

[@tech_Personality]

00:35 Iterative preorder traversal in binary tree 01:22 Iterative Preorder Traversal in Binary Tree is done using Stack 02:12 Iterative Preorder Traversal in Binary Tree using Stack 03:11 Iterative Preorder Traversal in Binary Tree using Stack 04:32 Importance of right side effects on mental strength 05:27 Iterative preorder traversal in binary tree is efficient and useful

[@Manasidas99]

Sir your teaching style is really unique.

[@manasgupta6647]

yep

[@shashibhushanrajput2461]

Nice simple explanation bhaiya.. please make a serious on medium and hard DP problems. Because right now DP is really in demand at Interviews.

[@lifehustlers164]

Completed 10/54(18% done)!!!

[@stith_pragya]

Thank You So Much for this wonderful video.....🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻

[@AdityaKumar-be7hx]

We can avoid a few extra checks to write a smaller code: class Solution { public: vector preorderTraversal(TreeNode* root) { vector preorder; stack st; st.push(root); while(!st.empty()){ auto curr=st.top(); st.pop(); if(curr!=nullptr){ preorder.push_back(curr->val); st.push(curr->right); st.push(curr->left); } } return preorder; } };

[@ScienceSeekho]

class Solution { public: // Recursive Traversal. TC: O(# of Nodes) ASC: O(height) void solve(TreeNode* root, vector &ans) { if(root == NULL) return; ans.push_back(root->val); solve(root->left, ans); solve(root->right, ans); } vector preorderTraversal(TreeNode* root) { vector ans; solve(root, ans); return ans; } // Iterative vector preorderTraversal(TreeNode* root) { vector ans; if(root == NULL) return ans; stack s; s.push(root); while(!s.empty()) { TreeNode* node = s.top(); s.pop(); ans.push_back(node->val); if(node->right) s.push(node->right); if(node->left) s.push(node->left); } return ans; } };

[@Ayusharma114]

we can use queue too how does that too working while using queue?

[@adityababu3405]

class Solution { public: vector preorderTraversal(TreeNode* root) { vector preorder; if(root == NULL) return preorder; stack st; st.push(root); while(!st.empty()) { root = st.top(); st.pop(); preorder.push_back(root->val); if(root->right != NULL) { st.push(root->right); } if(root->left != NULL) { st.push(root->left); } } return preorder; } };

[@noorjabeen731]

You are not a king.... You are a kingmaker ✨ 👑

[@ayushagrawal6473]

Very Nice way. I used to write the preorder code using the inorder traversal with slight updation.

[@tanishq2766]

I did the same, but I found this approach more intuitive !

[@sharmanihal99]

Just in case someone is looking for the python code for the above: class Solution: def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]: #Iterative Solution if not root:return stack=[root] ans=[] while stack: top=stack.pop() ans.append(top.val) if top.right: stack.append(top.right) if top.left: stack.append(top.left) return ans

[@cinime]

Understood! So amazing explanation as always, thank you very much!!

[@apmotivationakashparmar722]

Thank you So much Striver . Please upload Complete String in A-Z Dsa Sheet.

[@somyapratapsingh9849]

Looks like watch whole series in one go :))

[@per.seus._]

understood🌏

[@chiragbansal3364]

Awesome explanation in just 6 mins

[@nawabkhan4916]

great work, and have lots of sponsor ad so that you can provide great videos.

[@rahatsshowcase8614]

Recursion uses already stackspace But we are again usig that stack separately!Something new i likeit

[@prathameshjadhav2942]

Nice teaching bro.....

[@lavanyaprakashjampana933]

we love your content and we love you....

[@samuelfrank1369]

UNDERSTOOD. THANKS A LOT.

[@bhavkushwaha]

Thankyou Striver, Understood!

[@PranjalGunjanDiaries]

YOU ARE THE BEST..

[@vakhariyajay2224]

Thank you very much. You are a genius.

[@Learnprogramming-q7f]

Thank you Bhaiya

[@sonakshibajpai6445]

understood!! thanks striver

[@sonalisingh7932]

understood👍👍

[@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 kzbin.info/www/bejne/bKjbf5ZunKidbqc

[@BharatKumar-rc8vn]

cool stuff

[@coolgaurav5163]

Understoood

[@bhaveshkumar6842]

Immensely grateful for your content

[@SambhavJaincs23m060]

0:48 START

[@Ergoswami]

Completed!

[@sagarchauhan3187]

Hello Sir, Can you please complete the remaining videos of trees and graph of SDE sheet? please please upload!!🥺🥺

[@1tav0]

thank you so much for these series

[@sidvyas]

Bro once you explain most of the time I am able to code the logic by myself. Thanks so much man!!

[@DeadPoolx1712]

UNDERSTOOD;

[@nagavedareddy5891]

Huge respect..❤👏

[@anshikagupta5858]

Thankyou Striver:)

[@theSeniorSDE]

Striver, Completed this Question

[@mahaveerbana2031]

dil se thank you striver

[@PrashantSingh-jy6zp]

for best experience go to 0:48

[@pradipkumarmukhi]

Understood!!!

[@codeman3828]

Understood

[@culeforever5408]

understood

[@UECAshutoshKumar]

Thank you sir

[@bhushankorg5606]

Nice explaination!

[@jankeshchakravarthy9389]

Great video, I did not understand where are you printing?

[@_AkashRuidas]

great explaination

[@vakhariyajay315]

Thank you very much.

[@mriit3025]

I just realized how much I lost the time which should be used to understand the deep logic and the code will be automatic... In my second year of Btech, I had a DS (Data Structure) course, but I just understood the surface logicrememberedember the code mostly which was enough for getting 9/10. as iterative code was not important I was too lazy to understand it. so, my advice to myself is : Did you really understand? really? check? like. I completed a module in DS and just remembered the code, am I able to do a dry run of the code and understand the working! remember don't procastinate!

[@aditisharma5745]

You are the best!!

[@itsmepiyushsaha]

Superb explanation!

[@rohankrishnani]

Please make video on circular queue implementation as well

[@gangsta_coder_12]

Excellent explanation as always 🔥🔥🔥🔥🔥

[@codenchill732]

You made it so simple !! thanks alot

[@Mr.Indianwxvhehsy9191hghgx]

nice

[@kasyapdharanikota8570]

best explanation

[@sofikulmallick3766]

amazing explanation!

[@ramulala9365]

Great Explanation!

[@rexitspersonal8353]

converting recursive preorder to iterative public static List preorderTraversalSecond(Node root) { List ans = new ArrayList(); Stack ds = new Stack(); if (root == null) return ans; Node node = root; while (true) { if (node != null) { ans.add(node.val); ds.push(node); node = node.left; } else { if (ds.isEmpty()) break; node = ds.pop(); node = node.right; } } return ans; }

[@D44Aishwarya]

thanks a lot sir!

[@letmeinthefiend8522]

instead of taking right - left in stack.. can we use queue so that we can use left-right approch .. i learn preoder by rootleftright.. stack approach making confusion right before left

[@tejas7379]

No, it's not possible using queue. Regarding stack approach, think how stack works. Since right goes before left, left node will be popped and explored first, then the right node.

[@psibarpsi]

@@tejas7379 Why is it not possible to use queue here? Can you please elaborate?

[@tejas7379]

@@psibarpsi In stack we push right and left. Then when we pop we get left first and add its children to stack. So when we pop again we will be traversing all left children. So before we reach right part, we would have completely traversed left sub tree. Now lets say we use queue, we push left first and then right. [left, right]. So when we pop we get left first and then we push left's children to queue, like [right, (lefts children)]. When we pop again we will be exploring right subtree then again left sub tree's children. Which is wrong.

[@aakriti1]

@@tejas7379 Thanks for the nice explanation of why we're using a stack here and why we can't make use of a queue for this question.

[@tejas7379]

@@aakriti1 Glad it helped.

[@priyanshupandeypandey7994]

jiiiiiiiooooooo guru jiiiiiiii

[@akshaibaruah1720]

Beego of N (hehe love ur videos)

[@mriduljain1981]

completed lecture 9 of tree playlist

[@abhijeetbasfore6816]

Thank you

[@ganavin3423]

understood

[@yashmandaviya1356]

What is the purpose behind using extra space of the stack , its not improving the time complexity of the preorder traversal?

[@as_a_tester]

tysm striver bhai

[@Ankit.yt_885]

Great Work as always! :)

[@prateekverma9166]

THANKS STRIVER

[@utkarshsharma6650]

understoooood. thanks :)

[@harshitjaiswal9439]

Understoooooooood!!!

[@artitech6668]

Amazing

[@singhs_aniket]

Understood 👌👌

[@bhavya8608]

wonderfull!!

[@t-anime517]

Understood😊

[@senseiKakashi07]

this is somewhat like recursion, as recursion uses stack behind the scenes, right call tu wait kar mein pehle left hoke aata hu😂

[@kirtikhohal3313]

loll

[@mahaksharma7827]

👏👏👏👏

[@guruprasadkancharla5555]

why are we using stack? Is there any specific reason? We can do this using Queue also ?

[@harshsinha3221]

Queue should be used for Level order traversal, preorder traversal uses recursive call, so you can figure out that recursion itself uses stack DS

[@DevanshuAugusty]

shouldn't we take a temp node for root cause we dont want to modifie the data

[@sahilkumarsingh8517]

Understood😁

[@gauravkumar0777]

Op bhaiya

[@ajayypalsingh]

💚

[@nileshsinha7869]

Understood