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!
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.
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; }
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
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/
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
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()
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?
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?
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) !!!
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?
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
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)
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 🙏
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
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.
It's a good practice (an essential quality actually) in OOP to hide member variables and methods. This video beautifully explains OOP concepts: ua-cam.com/video/bSrm9RXwBaI/v-deo.html
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!
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.
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.
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!
u make great videos brother!
huge respects!
Is it possible through one stack ?
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.
Words are not enough to thank you for the amount of energy you put into teaching
After you gave the hint of stack, I paused the video and was able to solve on my own. Thank you Striver 😇
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;
}
};
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
The way you explain things are beyond expectations! The intuition goes straight in to the memory. Thanks for this awesome playlist!
Really loved your explanation. This series is on another level better than any paid course anywhere
Thanks a lot Striver !!!!
His Energy and Confidence is definitely inspiring for everyone :)
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;
}
};
Energy of Raj in this video is exceptional 😄🤟
Thank You So Much for this wonderful video.............🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻
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.
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/
how did you calculate average as o(1) , I didn't understood that part?
Search "amortized analysis"
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
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...
Explanation was so crisp and to the point. Thanks
Great video.
Keep on moving such videos.
Super content.
Bhayya u r super first I think it is complicated but ur teaching is like very simple and I really really understood it
Amazed by the solution, thanks for making it so fun Raj Bhaiya!!
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()
great man , nice approach
time complixity that striver mentioned is for average case which is O(1) in worst case the time complixity is O(N)
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();
}
}
Great Striver !
most amazing explanation on youtube :)
bruh, your energy is something else
Thank You Striver
.
.
.
.
.
and RELEVEL.
But in case of skewed bst, the space complexity will still be O(n)
Can be done in S.C: O(1) using Morris Traversal.
A good explanation for this problem💯.
Bro tum hi ho hmare liye jo ho thanks
Love u bro
Hats off to you!
This is the best vid explaining this problem on youtube I dare you. Thank you :)
Kya energy hai bhaiya🥰
Awesome approach👌👌 ...
I hope I can think like this someday on my own TT
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?
UNDERSTOOD;
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?
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) !!!
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)
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
Plz explain how time complexity is O(N/N) i.e., O(1)
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?
same thing happening with me too.
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
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
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)
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.
Answer storing is not considered
Can't we apply this approach in "Binary tree"? or why is it limited to "Binary Search Tree" only??
Thank You
Another approach may be to flatten the tree into inorder in O(h) space
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 🙏
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
@@ritikshrivastava9442 im having trouble with thought process
🥵 you are the reference for our sir. OP level videos broooo..🥵🥵🥵🥵🥵
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;
}
};
Basically the same idea of Inorder Traversal
Understood
we love your content and we love you.......🖤
Beautifully explained bro!!Thanks a lot!!
UNDERSTOOD
hello striver bhai, aap kounsa writing/digital pad use karte ho?
IPAD
LEETCODE 173 Problem;
Thank you sir
Dry run : 5:48
Thank you Bhaiya
Did not understand how time complexity is O(1)
Search "amortized analysis"
Great Explanation, Thanks
Thank you, very good explanation
Super explanation
Really liked the explanation
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.
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).
then height will be N too so O(H)=O(N) in that case
Thank you !!
your code is beautiful.
can someone explain why we used private in declaring stack and performing pushall function
It's a good practice (an essential quality actually) in OOP to hide member variables and methods. This video beautifully explains OOP concepts: ua-cam.com/video/bSrm9RXwBaI/v-deo.html
YOU ARE AWESOME MAN!!!!!!!!
Striver, you're the best.
understood
JAVA SOLUTION
class BSTIterator {
private Stack st = new Stack();
public BSTIterator(TreeNode root) {
pushAll(root);
}
public int next() {
TreeNode tmp = st.pop();
pushAll(tmp.right);
return tmp.val;
}
public boolean hasNext() {
return !st.isEmpty();
}
private void pushAll(TreeNode root)
{
for(;root!=null;root=root.left)
st.push(root);
}
}
please via dp ka series start karo . please
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!
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.
@@amanbhadani8840 bhaiya could u plz explain why TC is o(1) and not o(n) ?
@@joseph2073 Search "amortized analysis"
@@bhaveshkumar6842 ok thanks😀
understood.
5
/
4
/
3
/
2
/
1
in this case o(H) is O(n) so still the worst case space complexity is still O(N).
For skew o(n) for balance logn
ok just apply morris traversal , you will get your answer in O(1) space
TC:O(1) and SC:O(1) using morris traversal
class BSTIterator {
TreeNode curr;
public BSTIterator(TreeNode root) {
curr=root;
}
public int next() { //using morris traversal SC:O(1)
while(curr != null){
TreeNode store=curr;
if(curr.left==null){
curr=curr.right;
return store.val;
}
else{
TreeNode node=curr.left;
while(node.right != null && node.right != curr){
node=node.right;
}
if(node.right==null){
node.right=curr;
curr=curr.left;
}
else{
node.right=null;
curr=curr.right;
return store.val;
}
}
}
return 0;
}
public boolean hasNext() {
return curr != null;
}
}
4:25 - 7:49
50 done
does flattening bst will work??
yaa it will work ig. but we have to flatten it according to the inorder
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;
}
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;
}
};
```
why not use morris trversal and flantend binary tree to linked list
it will be o(1) approach
@@abcsumits space wise it will O(1)
If by any chance, someone wants the c++ solution of above ques. in O(1) space using Morris inorder Traversal-
class BSTIterator {
public:
TreeNode* curr;
BSTIterator(TreeNode* root) {
curr=root;
}
int morrisTraversal(){
int ans;
while(curr){
if(!curr->left){
ans=curr->val;
curr=curr->right;
break;
}
else{
TreeNode* prev=curr->left;
while(prev->right && prev->right!=curr) prev=prev->right;
if(prev->right==NULL){
prev->right=curr;
curr=curr->left;
}
else{
prev->right=NULL;
ans=curr->val;
curr=curr->right;
break;
}
}
}
return ans;
}
int next() {
return morrisTraversal();
}
bool hasNext() {
return !curr==NULL;
}
};
understood
Understood thanks :)
thanks, striver !!
What a Stuff !!
Understood
can anyone share the code for the follow up question for before() and hasBefore() methods ?
Thank you so much for this!!
Ok
Explanation 👌👏👍👍
Can anyone please explain this statement-- ?
for(; root!=NULL; st.push(root), root=root->left);
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.
@@aakriti1 i was writing the same thing
The personification 😂
Anyways thanks a lot!!
Nice ❤
Understood:)
Done!
1st august 2024 5.05 pm