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.❤💯

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

[@Ishan301]

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

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

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

[@thegreekgoat98]

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

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

[@vishalwaghmare3130]

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

[@Manasidas99]

Sir your teaching style is really unique.

[@manasgupta6647]

yep

[@lifehustlers164]

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

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

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

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

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

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

[@noorjabeen731]

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

[@apmotivationakashparmar722]

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

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

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

[@per.seus._]

understood🌏

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

[@cinime]

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

[@nawabkhan4916]

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

[@somyapratapsingh9849]

Looks like watch whole series in one go :))

[@rahatsshowcase8614]

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

[@chiragbansal3364]

Awesome explanation in just 6 mins

[@bhavkushwaha]

Thankyou Striver, Understood!

[@samuelfrank1369]

UNDERSTOOD. THANKS A LOT.

[@prathameshjadhav2942]

Nice teaching bro.....

[@lavanyaprakashjampana933]

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

[@PranjalGunjanDiaries]

YOU ARE THE BEST..

[@jankeshchakravarthy9389]

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

[@coolgaurav5163]

Understoood

[@Ergoswami]

Completed!

[@sonalisingh7932]

understood👍👍

[@BharatKumar-rc8vn]

cool stuff

[@sagarchauhan3187]

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

[@vakhariyajay2224]

Thank you very much. You are a genius.

[@yashmandaviya1356]

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

[@sidvyas]

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

[@sonakshibajpai6445]

understood!! thanks striver

[@pradipkumarmukhi]

Understood!!!

[@DeadPoolx1712]

UNDERSTOOD;

[@theSeniorSDE]

Striver, Completed this Question

[@bhaveshkumar6842]

Immensely grateful for your content

[@anshikagupta5858]

Thankyou Striver:)

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

[@nagavedareddy5891]

Huge respect..❤👏

[@rohankrishnani]

Please make video on circular queue implementation as well

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

[@SambhavJaincs23m060]

0:48 START

[@Learnprogramming-q7f]

Thank you Bhaiya

[@DevanshuAugusty]

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

[@1tav0]

thank you so much for these series

[@codeman3828]

Understood

[@PrashantSingh-jy6zp]

for best experience go to 0:48

[@mahaveerbana2031]

dil se thank you striver

[@itsmepiyushsaha]

Superb explanation!

[@UECAshutoshKumar]

Thank you sir

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

[@codenchill732]

You made it so simple !! thanks alot

[@gangsta_coder_12]

Excellent explanation as always 🔥🔥🔥🔥🔥

[@aditisharma5745]

You are the best!!

[@culeforever5408]

understood

[@vakhariyajay315]

Thank you very much.

[@aryansingh5198]

Why did we traverse the right sub tree first in pre order Arent we supposed to go from Root Left Right ???

[@bhushankorg5606]

Nice explaination!

[@_AkashRuidas]

great explaination

[@mahaksharma7827]

👏👏👏👏

[@kasyapdharanikota8570]

best explanation

[@Mr.Indianwxvhehsy9191hghgx]

nice

[@sofikulmallick3766]

amazing explanation!

[@ramulala9365]

Great Explanation!

[@mriduljain1981]

completed lecture 9 of tree playlist

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

[@harshitjaiswal9439]

Understoooooooood!!!

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

[@priyanshupandeypandey7994]

jiiiiiiiooooooo guru jiiiiiiii

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

[@laxmikantkatre4579]

I used little different approach to solve this question. I am pushing left first and then right in stack. Below is the Accepted Code: //Iterative Solution public List preorderTraversal(TreeNode root) { List ans = new LinkedList(); if(root == null) return ans; Stack stack = new Stack(); TreeNode node = root; while(true) { if(node != null) { stack.push(node); ans.add(node.val); node = node.left; } else { if(stack.isEmpty()) break; node = stack.pop(); node = node.right; } } return ans; }

[@singhs_aniket]

Understood 👌👌

[@koushik1261]

Bhaiya, in interviews do they ask explicitly to implement in iterative/recursive method?

[@D44Aishwarya]

thanks a lot sir!

[@prateekverma9166]

THANKS STRIVER

[@t-anime517]

Understood😊

[@as_a_tester]

tysm striver bhai

[@abhijeetbasfore6816]

Thank you

[@ravisaharan219]

Can someone please give an example of worst case scenario of space complexity where stack size goes up to O(N)

[@RAJ-cc4xn]

Can we do this Using Queue ? Anyone Please answer

[@ganavin3423]

understood

[@SachinSingh-id8mf]

bhaiya if you write a code in the video.. this would be more easy to understand.

[@akshaibaruah1720]

Beego of N (hehe love ur videos)

[@utkarshsharma6650]

understoooood. thanks :)

[@bhavya8608]

wonderfull!!