We can avoid the middle pointer also just keep updating the first and second pointers - class Solution { private TreeNode first; private TreeNode second; private TreeNode prev; public void recoverTree(TreeNode root) { inorder(root); int temp = first.val; first.val = second.val; second.val = temp; } public void inorder(TreeNode root) { if(root == null) return; inorder(root.left); // Keep updating first and second which points to first and second numbers to swap if(prev != null && root.val < prev.val) { if(first == null) { first = prev; second = root; } else { second = root; } } prev = root; inorder(root.right); } }
If trying to code in python use list to store prev,first,last and middle (or prev and last if not using middle) as when prev is just declared as just an argument, it gets reassigned and will not get passed on to the next recursive call.
find the two elements which are not at it's correct place through inorder traversal vector and sorted vector. again perform inorder traversal and have a check on root element if it's equal to incorrect element swap it.
🚨[IMPROVMENT IN THE CODE]:🚨 Hello Striver Bhaiya, 1- if you would have done middle = root in the else part then you wouldnt have had any requirement of the variable "last", you can do it using only two variables. 2- You could have also used an array of size 3 instead of global variables. But if your intention to was make code simpler for others to understand then it is all fine.....👍
i also solved it using two vaiables because if in first case we can find the prev value at which the root value is less than prev then that means we find the greater element so the next voilation is always less than the first voilation so we can store last as root
Shouldn't line number 24 of C++ be , if(prev ->Val != INT_MIN &&.....) rather than if(prev!=NULL &&....) because prev has already been set to a TreeNode with a value of INT_MIN so it will never be NULL?
just using "if(root->val < prev->val)" is fine as the first root->val will always be greater than the INT_MIN so it automatically won't check for the first node.
I guess it works for understanding the algorithm then optimising it to first and last become easier class Solution { TreeNode *prev; TreeNode *first; // TreeNode *middle; TreeNode *last; public: void inorder(TreeNode* root){ if(!root)return; inorder(root->left); // the node is not the root element if(prev != NULL and (root->val < prev->val)){ // if this is the first element if(first == NULL){ first = prev; } last = root; } prev = root; inorder(root->right); } void recoverTree(TreeNode* root) { prev = first = last = NULL; inorder(root);
yup, class Solution { TreeNode *prev; TreeNode *first; // TreeNode *middle; TreeNode *last; public: void inorder(TreeNode* root){ if(!root)return; inorder(root->left); // the node is not the root element if(prev != NULL and (root->val < prev->val)){ // if this is the first element if(first == NULL){ first = prev; } last = root; } prev = root; inorder(root->right); } void recoverTree(TreeNode* root) { prev = first = last = NULL; inorder(root);
Instead of using the middle pointer, we can solve this using only two pointers. Here is the detailed solution class Solution { public: TreeNode* prev = NULL; TreeNode* first = NULL; TreeNode* second = NULL; void inOrder(TreeNode*& root) { if (root == NULL) return; inOrder(root->left); if (prev == NULL) prev = root; else { if (prev->val > root->val) { if (first == NULL) { first = prev; second = root; } else { second = root; } } } prev = root; inOrder(root->right); } void recoverTree(TreeNode* root) { inOrder(root); if (first == NULL) return; swap(first->val, second->val); return; } };
Bhai I think prev is never going to be NULL, because at first we are assigning it with INT_MIN and after that it always stores non-null root value. Wo condition hata ke dekho code chalega
@@Xp-Sam ha prev ko NULL kar de instead of INT_MIN tabh bhi chalega, my code without middle pointer, easy to optimize if yo examine the conditions in main function: class Solution { TreeNode *prev; TreeNode *first; // TreeNode *middle; TreeNode *last; public: void inorder(TreeNode* root){ if(!root)return; inorder(root->left); // the node is not the root element if(prev != NULL and (root->val < prev->val)){ // if this is the first element if(first == NULL){ first = prev; } last = root; } prev = root; inorder(root->right); } void recoverTree(TreeNode* root) { prev = first = middle = last = NULL; inorder(root);
Is it not possible that there are more than two violations for example three or four violations? Why have we considered that either there will be one violation or two violations?
Please like and share :)
What a co incidence, I was exactly studying the same problem and wasn't able to understand on my own and here comes Striver for rescue 😀😀
instead of making third variable we can also update the middle variable when there is a 2nd violation
As u initialize prev as INT_MIN then u don't need to check prev != null in inorder recursive. Just correction. You are already great.
In leetcode question the values are in range of [INT_MIN, INT_MAX], so this won't work there.
We can avoid the middle pointer also just keep updating the first and second pointers -
class Solution {
private TreeNode first;
private TreeNode second;
private TreeNode prev;
public void recoverTree(TreeNode root) {
inorder(root);
int temp = first.val;
first.val = second.val;
second.val = temp;
}
public void inorder(TreeNode root) {
if(root == null) return;
inorder(root.left);
// Keep updating first and second which points to first and second numbers to swap
if(prev != null && root.val < prev.val) {
if(first == null) {
first = prev;
second = root;
} else {
second = root;
}
}
prev = root;
inorder(root.right);
}
}
Thought same ✌️💯
my mom said "ye ladka kitni mehnat karta h" - what a explanation striver bhaiya
Hare Krishna..!
Got Placed in R & D of a Product Based Company..!
Thanks Bhaiya..!
I will tag you in Linkedln post in some time
add morris traversal and we can do this problem on O(1) space as well.
You are the best instructor !! Thanks a ton for this content ! You are bringing a revolution striver!
LeetCode 99 problem Can be done with morris traversal
Thank You So Much for this wonderful video...🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻
If trying to code in python use list to store prev,first,last and middle (or prev and last if not using middle) as when prev is just declared as just an argument, it gets reassigned and will not get passed on to the next recursive call.
Such a brilliant explanation of the problem! Thank you very much fir helping all of us!
Thankyou sir👍For always helping by your approaches
find the two elements which are not at it's correct place through inorder traversal vector and sorted vector. again perform inorder traversal and have a check on root element if it's equal to incorrect element swap it.
🚨[IMPROVMENT IN THE CODE]:🚨
Hello Striver Bhaiya,
1- if you would have done middle = root in the else part then you wouldnt have had any requirement of the variable "last", you can do it using only two variables.
2- You could have also used an array of size 3 instead of global variables.
But if your intention to was make code simpler for others to understand then it is all fine.....👍
i also solved it using two vaiables because if in first case we can find the prev value at which the root value is less than prev then that means we find the greater element so the next voilation is always less than the first voilation so we can store last as root
//first brute method
vectorv;
int i=0;
void tra(Node *root)
{
if(!root) return;
tra(root->left);
v.push_back(root->data);
tra(root->right);
}
void check(Node *root)
{
if(!root) return;
check(root->left);
if(v[i]!=root->data)
{
swap(root->data,v[i]);
}
i++;
check(root->right);
}
void correctBST( struct Node* root )
{
tra(root);
sort(v.begin(),v.end());
check(root);
}
After watching your tree series i m pretty confident in Binary trees and bst 🔥🔥🔥🔥🔥🔥🔥
This dude's neighbors get free lectures. Hope they appreciate it.
Absolutely brilliant explanation as well as mind blowing implementation of code,just loved it bhaiya.
The logic you have given to solve this is brilliant af. GG
excellent explanation striver bhai
I always feel motivated by your passion of explaining problems👍
Much Love from London❤
i think there is no need of " prev != null" in line 27
Watch these videos, and you'll never forget the importance of inorder traversal for BSTs!
Thank you striver bhaiya for making such a great series and it's helping me out in placement preparation
You seem to like teddy bears a lot
Awesome explanation
Brute force Code:
class Solution {
public:
void inorderTraversal(TreeNode* root,vector&arr){
if(root==NULL)
return;
inorderTraversal(root->left,arr);
arr.push_back(root->val);
inorderTraversal(root->right,arr);
}
void recoverBST(TreeNode* root, vector&arr,int &i){
if(root==NULL)
return;
recoverBST(root->left,arr,i);
if(root->val != arr[i]){
root->val = arr[i];
}
i++;
recoverBST(root->right,arr,i);
}
void recoverTree(TreeNode* root) {
vectorarr;
inorderTraversal(root,arr);
sort(arr.begin(),arr.end());
// for(auto ar:arr)cout
We have to make variable i, a global variable. So, that it can get updated after every recursive call.
Shouldn't line number 24 of C++ be , if(prev ->Val != INT_MIN &&.....) rather than if(prev!=NULL &&....) because prev has already been set to a TreeNode with a value of INT_MIN so it will never be NULL?
just using "if(root->val < prev->val)" is fine as the first root->val will always be greater than the INT_MIN so it automatically won't check for the first node.
For many problems in BST,
MORRIS Inorder approach is giving Stack Overflow error (RUN TIME ERROR).
Is it same with everybody ?
Very helpful and thorough explanation, love it!
even if we keep all variables and functions of class in public, code still works. But why are we keeping private for some functions and variables ?
Congratulations on 3 Lakh Subscribers
13:55 which online coding judge or editor is that??
but what if there are more than one nodes that are swapped?
15:20 the ans is comming incorrect if we just swap the 49 and 50th line but Y case to un mein se ek hi chlega aggy peeechy sy kya farak pdta hai
Quite ambiguous explanation.
Why you have used middle,we can just update last instead of middle and it works fine??
ua-cam.com/video/k2haMtP7nvs/v-deo.html
I guess it works for understanding the algorithm then optimising it to first and last become easier
class Solution {
TreeNode *prev;
TreeNode *first;
// TreeNode *middle;
TreeNode *last;
public:
void inorder(TreeNode* root){
if(!root)return;
inorder(root->left);
// the node is not the root element
if(prev != NULL and (root->val < prev->val)){
// if this is the first element
if(first == NULL){
first = prev;
}
last = root;
}
prev = root;
inorder(root->right);
}
void recoverTree(TreeNode* root) {
prev = first = last = NULL;
inorder(root);
swap(first->val,last->val);
}
};
@@your_name96 thanks bro btw which are u a college student?
@@justinmyth4980 Islamabad university , lahore
Which device is used in videos?? I need one to practice.
what drawing software are u using?
the first method can be optimised to O(n) + O(n) time, by removing the redundant sorting,
void dfs(Node* root, vector &inorder){
if(root == NULL) return;
dfs(root->left, inorder);
inorder.push_back(root);
dfs(root->right, inorder);
}
void correctBST( struct Node* root )
{
vector inorder;
dfs(root, inorder);
int ct = 0;
vector pos;
for(int i = 1; i < inorder.size(); i++){
if(inorder[i]->data < inorder[i-1]->data){
pos.push_back(i);
ct++;
}
}
if(ct == 1){
swap(inorder[pos[0] - 1]->data, inorder[pos[0]]->data);
}
else if(ct == 2){
swap(inorder[pos[0]-1]->data, inorder[pos[1]]->data);
}
}
Thanks Man!!!
The middle pointer can be avoided I guess!!!
ua-cam.com/video/k2haMtP7nvs/v-deo.html
yup,
class Solution {
TreeNode *prev;
TreeNode *first;
// TreeNode *middle;
TreeNode *last;
public:
void inorder(TreeNode* root){
if(!root)return;
inorder(root->left);
// the node is not the root element
if(prev != NULL and (root->val < prev->val)){
// if this is the first element
if(first == NULL){
first = prev;
}
last = root;
}
prev = root;
inorder(root->right);
}
void recoverTree(TreeNode* root) {
prev = first = last = NULL;
inorder(root);
swap(first->val,last->val);
}
};
If the inorder sequence is 3 25 7 8 10 15 20 12. Then...
Why prev = new Tree(INT_MIN)
That is not required !!!!
Pls Anyone ???
I simply made the prev node NULL and the code still got accepted.
Just wow, the intution was awesome.
Thank you Bhaiya
Great explanation , thank you.
good video
Instead of using the middle pointer, we can solve this using only two pointers. Here is the detailed solution
class Solution {
public:
TreeNode* prev = NULL;
TreeNode* first = NULL;
TreeNode* second = NULL;
void inOrder(TreeNode*& root) {
if (root == NULL)
return;
inOrder(root->left);
if (prev == NULL)
prev = root;
else
{
if (prev->val > root->val)
{
if (first == NULL)
{
first = prev;
second = root;
}
else
{
second = root;
}
}
}
prev = root;
inOrder(root->right);
}
void recoverTree(TreeNode* root) {
inOrder(root);
if (first == NULL)
return;
swap(first->val, second->val);
return;
}
};
We dont need to check the condition if prev!=NULL ;
can someone tell me why in the last we do (prev=root ) pls if u know try to give a explanation...🙏
Thank you so much striver bhaiya for providing such an amazing content :)
Why you need to allocate space to prev? I don’t think we need it.
ua-cam.com/video/k2haMtP7nvs/v-deo.html
If bst is not in correct order you will not get the preorder sorted
Great Explanation !!!
we love your content and we love you......🤟🖤
When this Series Complete
class Solution {
TreeNode prev;
TreeNode violation1;
TreeNode violation2;
public void inorder(TreeNode root) {
if(root == null)
return;
inorder(root.left);
if(prev != null && prev.val > root.val)
{
if(violation1 == null)
violation1 = prev;
violation2 = root;
}
prev = root;
inorder(root.right);
}
public void recoverTree(TreeNode root) {
inorder(root);
int temp = violation1.val;
violation1.val = violation2.val;
violation2.val = temp;
}
}
Thx
Amazing explanation bhaiya!
fire hai bhau
understood
Excellent explanation
When this Serie Complete
Tomorrow..
@@takeUforward cool
Thank you sir
why are we checking prev != NULL
tabhi toh compare kr payega bhai swapping ke lie
Bhai I think prev is never going to be NULL, because at first we are assigning it with INT_MIN and after that it always stores non-null root value.
Wo condition hata ke dekho code chalega
@@Xp-Sam ha prev ko NULL kar de instead of INT_MIN tabh bhi chalega, my code without middle pointer, easy to optimize if yo examine the conditions in main function:
class Solution {
TreeNode *prev;
TreeNode *first;
// TreeNode *middle;
TreeNode *last;
public:
void inorder(TreeNode* root){
if(!root)return;
inorder(root->left);
// the node is not the root element
if(prev != NULL and (root->val < prev->val)){
// if this is the first element
if(first == NULL){
first = prev;
}
last = root;
}
prev = root;
inorder(root->right);
}
void recoverTree(TreeNode* root) {
prev = first = middle = last = NULL;
inorder(root);
swap(first->val,last->val);
}
};
Don't use middle pointer just 2nd one if found
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
TreeNode ptr1=null;
TreeNode ptr2=null;
TreeNode prev=null;
public void getAns(TreeNode root){
if(root==null){
return;
}
getAns(root.left);
if(prev != null && root.val< prev.val){
if(ptr1==null){
ptr1 =prev;
ptr2=root;
}
else{
ptr2=root;
}
}
prev=root;
getAns(root.right);
}
public void recoverTree(TreeNode root) {
getAns(root);
int temp=ptr1.val;
ptr1.val=ptr2.val;
ptr2.val=temp;
}
}
bhai code bahut tej explain karte ho thoda slow karo yaar
understood.
Java Solution 👇
class Solution {
private TreeNode firstViolation = null;
private TreeNode adjacentToViolation = null;
private TreeNode secondViolation = null;
private TreeNode prev = null;
private void swap(TreeNode a, TreeNode b) {
int temp = a.val;
a.val = b.val;
b.val = temp;
}
private void helper(TreeNode root) {
if (root == null) {
return;
}
// Traverse the left subtree
helper(root.left);
// Check for violations
if (prev != null && root.val < prev.val) {
if (firstViolation == null) {
firstViolation = prev;
adjacentToViolation = root;
} else {
secondViolation = root;
}
}
// Update prev to current node
prev = root;
// Traverse the right subtree
helper(root.right);
}
public void recoverTree(TreeNode root) {
helper(root);
if (secondViolation == null) {
swap(firstViolation, adjacentToViolation);
} else {
swap(firstViolation, secondViolation);
}
}
}
Perfectly explained....
Thanks for the video man.
Check out Morris Inorder traversal code related to these problem
class Solution {
public:
void recoverTree(TreeNode* root) {
if(!root){
return;
}
TreeNode*cand1=NULL;
TreeNode*cand2=NULL;
TreeNode*prev=NULL;
TreeNode*curr=root;
while(curr){
if(curr->left==NULL){
if(prev){
if(prev->val > curr->val){
if(cand1==NULL){
cand1=prev;
}
cand2=curr;
}
}
prev=curr;
curr=curr->right;
}
else{
TreeNode*temp=curr->left;
while(temp && temp->right && temp->right!=curr){
temp=temp->right;
}
if(temp->right==NULL){
temp->right=curr;
curr=curr->left;
}
else{
if(prev){
if(prev->val > curr->val){
if(cand1==NULL){
cand1=prev;
}
cand2=curr;
}
}
prev=curr;
temp->right=NULL;
curr=curr->right;
}
}
}
swap(cand1->val,cand2->val);
}
};
```
class Solution {
private:
TreeNode *first;
TreeNode *last;
TreeNode *prev;
void inorder(TreeNode* root){
if(root==NULL) return;
inorder(root->left);
if(prev->val>root->val){
if(first==NULL){
first=prev;
last=root;
}
else{
last=root;
}
}
prev=root;
inorder(root->right);
}
public:
void recoverTree(TreeNode* root) {
first=last=prev=NULL;
prev=new TreeNode(INT_MIN);
inorder(root);
swap(first->val,last->val);
}
};
```
Exceptional.
Great explain
Is it not possible that there are more than two violations for example three or four violations? Why have we considered that either there will be one violation or two violations?
Because the question states that only 2 nodes will be swapped
hey guys'
bhaiya you are great
Thank You : )
this was smooth!
Hey interviewer😆😅
understood
Understood thanks :)
nice code explanation
Understood!
striver rescued me here
shouldnt first be equal to root..how come first is set equal to prev
Done!!
Great video
Understood:)
Can I do it using the concept which you are using in the last lecture (largest bst) when the condition get wrong
largest of left
ua-cam.com/video/k2haMtP7nvs/v-deo.html
13:10
💚
Goat 🐐
Wow
...............
Baak bakwas krta h Khali kuch sahi se explain nhi krta h