L50. Binary Search Tree Iterator | BST | O(H) Space

[@takeUforward]

Please do like, that is the only thing which keeps me motivated to make such kind of videos! Your support is all I need :) Follow-up question: Design before and hasBefore!

[@siddharthvs1770]

u make great videos brother! huge respects!

[@sayantaniguha8519]

Is it possible through one stack ?

[@ritikshandilya7075]

someone asked me : Who is Striver ? My Answer : Striver is a person sent by God to help the helpless and beginners without any self benefit .The person responsible to help the entire community single handedly. Thankyou so much Striver for great explanation.

[@rachanasingh2231]

Words are not enough to thank you for the amount of energy you put into teaching

[@prachigoyal2510]

After you gave the hint of stack, I paused the video and was able to solve on my own. Thank you Striver 😇

[@pritishpattnaik4674]

Very Beautifully explained Striver bhaiya , wrote the code without seeing the solution In case anybody needs the code , (Done by my own) : class BSTIterator { public: stack st; BSTIterator(TreeNode* root) { //push all the left nodes in the stack while (root != NULL){ st.push(root); root = root->left; } } int next() { TreeNode *currNode = st.top(); st.pop(); if (currNode->right != NULL){ TreeNode *temp = currNode->right; while (temp != NULL){ st.push(temp); temp = temp->left; } } return currNode->val; } bool hasNext() { if (!st.empty()) return true; return false; } };

[@satyapraneethkatta1652]

Really loved your explanation. This series is on another level better than any paid course anywhere Thanks a lot Striver !!!!

[@anupamdungdung9417]

The way you explain things are beyond expectations! The intuition goes straight in to the memory. Thanks for this awesome playlist!

[@BhavanaG-j9e]

Striver, Thank you for the detailed explanation, It was really helpful Python Solution: class BSTIterator: def __init__(self, root: Optional[TreeNode]): self.stack = [] self.pushAllLeft(root) def next(self) -> int: if self.stack: value = self.stack.pop() self.pushAllLeft(value.right) return value.val def hasNext(self) -> bool: if not self.stack: return False return True def pushAllLeft(self,node): while node: self.stack.append(node) node=node.left

[@stith_pragya]

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

[@bhairavas2528]

His Energy and Confidence is definitely inspiring for everyone :)

[@yashjain1492]

how did you calculate average as o(1) , I didn't understood that part?

[@bhaveshkumar6842]

Search "amortized analysis"

[@vishious14]

Thanks Striver, I was able to code this on my own as soon as you mentioned stack and going right as soon as you pop an element.

[@nandpatel924]

Explanation was so crisp and to the point. Thanks

[@utkarshsaxena7445]

Easy Solution ✔✔ class BSTIterator { public: vector ans; int pos; void inorder(TreeNode *root) { if(root==NULL) return; inorder(root->left); ans.push_back(root->val); inorder(root->right); } BSTIterator(TreeNode* root) { pos=0; inorder(root); } int next() { return ans[pos++]; } bool hasNext() { return ans.size()!=pos; } };

[@pulkitjain5159]

if it was allowed to break the tree , we could apply the morris traversal , and could create the linked list of inorder traversal with the same tree , by this we would not use space complexity of O(N) . but ya only if it is allowed to make changes in the tree

[@rohithpeddi]

A solution using Morris Traversal: Time Complexity for next and hasNext: O(1) Space complexity : O(1) class BSTIterator { public: TreeNode* curr = NULL; BSTIterator(TreeNode* root) { TreeNode* c = root, *last = NULL; while(c) { if (!c->left) { if (!last) last = c; else last->right = c, last = c; c = c->right; } else { TreeNode* x = c->left; while(x->right&&x->right!=c) x = x->right; if (x->right) { if (!last) last = c; else last->right = c, last = c; c = c->right; } else x->right = c, c = c->left; } } while(root->left) root=root->left; curr = root; } int next() { int ans = curr->val; curr=curr->right; return ans; } bool hasNext() { return curr; } }; Link for solution: leetcode.com/problems/binary-search-tree-iterator/solutions/3608539/morris-traversal-most-efficient/

[@jaiminsolanki5478]

Amazed by the solution, thanks for making it so fun Raj Bhaiya!!

[@Zero-ss6pn]

Energy of Raj in this video is exceptional 😄🤟

[@tarunsharma2971]

Video with your expression is like you are sitting in front of me and here comes the twist that I need to insert this algorithm in my stack...

[@paragroy5359]

Great video. Keep on moving such videos. Super content.

[@joichirogaming]

Awesome approach👌👌 ... I hope I can think like this someday on my own TT

[@leepakshiyadav1643]

most amazing explanation on youtube :)

[@lavanyaprakashjampana933]

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

[@manasranjanmahapatra3729]

A good explanation for this problem💯.

[@sakshisinghal1669]

Why the Time complexity is O(1) at 4:28? If we are considering stack space to store the inorder then we should consider time to get inorder as well even if getting next and hasNext() are constant. Can @striver or anyone please explain?

[@anonymousvoid6356]

Sakshi, The time complexity to create the inorder traversal in the form of array is considered as a prepocessing step (we are doing it just once) We are worried only about the time complexity of the individual calls to the iterator. So TC is O(1) !!!

[@anmoldarak]

Yes.. you are right.. when someone is calling next, in worst case we have to traverse through the height of the binary tree which is O(logn)

[@harpercfc_]

This is the best vid explaining this problem on youtube I dare you. Thank you :)

[@RavinderSingh-qb4xi]

couldn't understand how T.C is O(1) at 4:32 as we are storing in vector so it must take O(N) to do so.

[@takeUforward]

Answer storing is not considered

[@tps8470]

Thank You

[@tusharnain6652]

Thank You Striver . . . . . and RELEVEL.

[@gaurigupta5129]

Hats off to you!

[@karanthakur11]

Dry run : 5:48

[@evolver92]

time complixity that striver mentioned is for average case which is O(1) in worst case the time complixity is O(N)

[@apmotivationakashparmar722]

Great Striver !

[@vibhu613]

Kya energy hai bhaiya🥰

[@sanjaykeshwar2100]

Can be done in S.C: O(1) using Morris Traversal.

[@pjagannadham2540]

Bhayya u r super first I think it is complicated but ur teaching is like very simple and I really really understood it

[@atharvakulkarni2024]

Beautifully explained bro!!Thanks a lot!!

[@AdityaKumar-be7hx]

If anyone is wondering how to solve the merging of BST - here's my solution using the iterator ( I added peek() to make it easier to compare. class BSTIterator{ private: stackst; public: BSTIterator(Node* root){ push_all(root); } //return if more elements are left in tree traversal or not. bool hasNext(){ return !st.empty(); } //return the next item in inorder traversal. int next(){ Node* temp=st.top(); st.pop(); if(temp->right){ push_all(temp->right); } return temp->data; } int peek(){ return st.top()->data; } private: void push_all(Node* root){ while(root){ st.push(root); root=root->left; } } }; class Solution { public: //Function to return a list of integers denoting the node //values of both the BST in a sorted order. vector merge(Node *root1, Node *root2) { vector ans; BSTIterator a(root1); BSTIterator b(root2); while(a.hasNext() and b.hasNext()){ if(a.peek()

[@pulkitjain5159]

great man , nice approach

[@DeadPoolx1712]

UNDERSTOOD;

[@Learnprogramming-q7f]

Thank you Bhaiya

[@editorera239]

Bro tum hi ho hmare liye jo ho thanks Love u bro

[@vivek5144]

Guru ji can u please tell me how i improve my thought process about the questions. Jaadtar question me help leni padti h aapki videos ki, solution to soch leta hu ki aise krunga but code likhne me problem hoti h. Agr time mile to please reply kar dijiyega 🙏

[@ritikshrivastava9442]

if you can think the solution and not able to code then you don't have command over the language whatever the language you have chosen try to clear basics of it

[@HemanthKumar-bl1yt]

@@ritikshrivastava9442 im having trouble with thought process

[@bhagyashreekhairnar683]

Thank you !!

[@deekshithtirumala6474]

🥵 you are the reference for our sir. OP level videos broooo..🥵🥵🥵🥵🥵

[@AmanKumar-xw5bs]

But in case of skewed bst, the space complexity will still be O(n)

[@yuzhou9893]

bruh, your energy is something else

[@AnshKumar-dp1st]

Can't we apply this approach in "Binary tree"? or why is it limited to "Binary Search Tree" only??

[@rohanprasad97]

Can anyone help me understand how the Space Complexity is O(H), since we are putting all the elements in the stack (check the stack at 10:55), if we are pushing all the elements then the Space Complexity should be O(N) right? Any help will be really appreciated!

[@amanbhadani8840]

Here space complexity is the height of BST because if you see carefully at any moment of time stack only contains the number of nodes at max the height of tree.Because what we are doing ,simply take out the top element of stack and pop it out and push all its left left left .....element so it can go max to max the height of tree. You will not find any moment where stack containing all the nodes because we are also popping out the top element. At 10:55 stack is actually empty,space complextiy is the size of stack and is analysed by the max no of nodes that is present at any particular instant of time.Hope all your doubts are cleared now.

[@joseph2073]

@@amanbhadani8840 bhaiya could u plz explain why TC is o(1) and not o(n) ?

[@bhaveshkumar6842]

@@joseph2073 Search "amortized analysis"

[@joseph2073]

@@bhaveshkumar6842 ok thanks😀

[@SibiRanganathL]

Understood

[@niharikamurulidhara7017]

Plz explain how time complexity is O(N/N) i.e., O(1)

[@theLonelyBandit6984]

Another approach may be to flatten the tree into inorder in O(h) space

[@Tatiana-zu1gf]

Thank you, very good explanation

[@anmoldarak]

I think TC is not O(1), it is O(logn) because when you are calling next, in worst case scenario you need to traverse entirely through the height of the tree (approximately). Hence O(logn)

[@yashmundada2483]

Aren't we storing the nodes in the stack... Doesn't that make the time complexity worse than the inorder traversal where we are only storing the values. Since a node could have in the worst case (root) info about N other nodes?

[@per.seus._]

UNDERSTOOD

[@UECAshutoshKumar]

Thank you sir

[@nishantgautam4343]

Hey everyone, I coded this using both approaches, one with T.C. O(n) & S.C. O(n) using arrayList, and the other with Stack which is T.C. O(n) & S.C. O(h). But at leetcode the first one took both less time and space, which is unusual. Did it happen with you all too?

[@abhirupbasu3386]

same thing happening with me too.

[@HimanshuYadav-pp2ue]

bro don't see space and time which leetcode show as it depend on leetcode server it will vary every time you submit the same code

[@pulkitjain5159]

yeh may be he used morris traversal to convert same tree to a linked list , just like what we did in flatten tree , and after getting a linked list it would be easier then

[@shivamverma-mt6kp]

Great Explanation, Thanks

[@noobcreations9556]

hello striver bhai, aap kounsa writing/digital pad use karte ho?

[@dipeshsaili4468]

IPAD

[@harshitjaiswal9439]

understood.

[@iamloking]

Really liked the explanation

[@chiragbansod8252]

understood

[@harshapriyaannapureddy5103]

Did not understand how time complexity is O(1)

[@bhaveshkumar6842]

Search "amortized analysis"

[@GirishJain]

Basically the same idea of Inorder Traversal

[@Panichusko]

class BSTIterator { public: void inorder(TreeNode* root , vector& v1) { if(!root)return; inorder(root->left,v1); v1.push_back(root->val); inorder(root->right,v1); } vector v1; int i=0; BSTIterator(TreeNode* root) { inorder(root,v1); } int next() { i++; return v1[i-1]; } bool hasNext() { if(i+1

[@abhaytiwari6411]

Explanation 👌👏👍👍

[@suryakiran2970]

Super explanation

[@karthik-varma-1579]

class BSTIterator { Stack st; public BSTIterator(TreeNode root) { st = new Stack(); addLeft(root); } public void addLeft(TreeNode root){ TreeNode cur = root; while(cur!=null){ st.push(cur); cur = cur.left; } } public int next() { TreeNode peek = st.pop(); if(peek.right!=null) addLeft(peek.right); return peek.val; } public boolean hasNext() { return !st.isEmpty(); } }

[@i_m_mandeep_singh8365]

YOU ARE AWESOME MAN!!!!!!!!

[@sanskrutishahu517]

does flattening bst will work??

[@pulkitjain5159]

yaa it will work ig. but we have to flatten it according to the inorder

[@tanmayjain5821]

How is space complexity O(H)? in the worst case we can have n element all on the left which will bring up space complexity to O(N).

[@txbankush4601]

then height will be N too so O(H)=O(N) in that case

[@ritishkalia2487]

can someone explain why we used private in declaring stack and performing pushall function

[@bhaveshkumar6842]

It's a good practice (an essential quality actually) in OOP to hide member variables and methods. This video beautifully explains OOP concepts: kzbin.info/www/bejne/mITVnmyIjdx1l6s

[@krishnaradhey2814]

LEETCODE 173 Problem;

[@ritikshrivastava9442]

5 / 4 / 3 / 2 / 1 in this case o(H) is O(n) so still the worst case space complexity is still O(N).

[@only_for_fun1234r]

For skew o(n) for balance logn

[@pulkitjain5159]

ok just apply morris traversal , you will get your answer in O(1) space

[@kmindu9616]

Thank you so much for this!!

[@leetcoder1159]

Ok

[@bhaveshkumar6842]

Striver, you're the best.

[@GURU-lz1iw]

Can you solve it using linked list. I mean we can do inorder traversal ans store each node in a linked list and then iterate over it... Can you please share the code for the same.

[@AkashBisht-cq3ys]

1st august 2024 5.05 pm

[@abcsumits]

why not use morris trversal and flantend binary tree to linked list

[@abcsumits]

it will be o(1) approach

[@pulkitjain5159]

@@abcsumits space wise it will O(1)

[@Anonymous-uj3jx]

Understood thanks :)

[@venutalla5932]

❤❤❤

[@prajitbanerjee8226]

your code is beautiful.

[@jatinarya3514]

50 done

[@bibhabendumukherjee9247]

please via dp ka series start karo . please

[@vaalarivan_p]

4:25 - 7:49

[@AKASHKUMAR-li7li]

class BSTIterator { stack st; public: BSTIterator(TreeNode* root) { st.push({root, 0}); } int next() { while(!st.empty()){ pair tp = st.top(); if(tp.second == 0){ st.top().second++; if(tp.first->left) st.push({tp.first->left, 0}); } else if(tp.second == 1){ int val = tp.first->val; st.pop(); if(tp.first->right) st.push({tp.first->right, 0}); return val; } else { st.pop(); } } return -1; } bool hasNext() { if(!st.empty()) return true; return false; } };

[@roopeshn3301]

Understood

[@dineshchintu9779]

thanks, striver !!

[@goooo9561]

Using morris traversal : TreeNode* cur; BSTIterator(TreeNode* root) { cur=root; } int next() { if(cur->left==NULL) { int value=cur->val; cur=cur->right; return value; } else{ while(cur->left!=NULL) { TreeNode *pre=cur->left; while(pre->right&&pre->right!=cur) { pre=pre->right; } if(pre->right==NULL) { pre->right=cur; cur=cur->left; } else{ pre->right=NULL; int value=cur->val; cur=cur->right; return value; } } int value=cur->val; cur=cur->right; return value; } return -1; } bool hasNext() { return cur!=NULL; }

[@casinarro]

The personification 😂 Anyways thanks a lot!!

[@tushar5359]

Nice ❤

[@rishabhgupta9846]

understood

[@khushinaudiyal2786]

Can anyone please explain this statement-- ? for(; root!=NULL; st.push(root), root=root->left);

[@aakriti1]

You can use below snippet too: while(root!=NULL) { stk.push(root); root=root->left; } Both snippets basically means that keep pushing all the left nodes of the root in the stack till the root is not equal to the NULL.

[@only_for_fun1234r]

@@aakriti1 i was writing the same thing

[@girikgarg8]

Done!

[@mrrishiraj88]

Thanks a lot👍

[@vineethkumar8273]

can anyone share the code for the follow up question for before() and hasBefore() methods ?

[@ajayypalsingh]

💚

[@AshokKumar-ii4qr]

I can code but can't calculate time complexity 🙂

[@danishmukhtar9250]

We can optimise space to O(1) if we use morris traversal ``` class BSTIterator { public: TreeNode* cur = NULL; pair NextMoris(TreeNode* root){ while(root!=NULL){ if(root->left==NULL){ int ans = root->val; root = root->right; return {ans,root}; }else{ TreeNode* node = root->left; while(node->right && node->right!=root){ node = node->right; } if(node->right == NULL){ node->right = root; root = root->left; }else{ root = node->right; int ans = root->val; root = root->right; node->right = NULL; return {ans,root}; } } } return {0,NULL}; } BSTIterator(TreeNode* root) { cur = root; } int next() { pair p = NextMoris(cur); cur = p.second; return p.first; } bool hasNext() { return cur!=NULL; } }; ```

[@iamnoob7593]

US