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

#treeSeries #striver #placements

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

[ritikshandilya]

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.

[rachanasingh]

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

[prachigoyal]

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

[pritishpattnaik]

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<TreeNode*> 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;
}
};

[anupamdungdung]

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

[satyapraneethkatta]

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

[ibozkxo]

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()

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

[utkarshsaxena]

Easy Solution ✔✔
class BSTIterator {
public:
vector<int> 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;
}
};

[bhairavas]

His Energy and Confidence is definitely inspiring for everyone :)

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

[yashjain]

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

[Zero-sspn]

Energy of Raj in this video is exceptional 😄🤟

[vishious]

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.

[pulkitjain]

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

[tarunsharma]

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

[AmanKumar-xwbs]

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

[nandpatel]

Explanation was so crisp and to the point. Thanks

[AdityaKumar-behx]

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:
stack<Node*>st;

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<int> merge(Node *root1, Node *root2)
{
vector<int> ans;
BSTIterator a(root1);
BSTIterator b(root2);

while(a.hasNext() and b.hasNext()){
if(a.peek()<=b.peek()){
ans.push_back(a.next());
} else {
ans.push_back(b.next());
}
}

while(a.hasNext()) ans.push_back(a.next());

while(b.hasNext()) ans.push_back(b.next());

return ans;
}
};

[jaiminsolanki]

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