Flatten BST to sorted list | Magic Of Recursion | Recursion Concepts And Questions | Video 12

[@codestorywithMIK]

Video-11
CORRECTION :
We are visiting from head for every further nodes in tree to connect. So, Time will be O(n^2) but this can be reduced to O(n) if we keep track of the last node of the list we have formed. See the code below :
/******** ************************C++ ********************************/
class Solution
{
public:
Node* prev = NULL;
Node *flattenBST(Node *root) {
if(!root) {
return NULL;
}
Node* head = flattenBST(root->left); //Trust
root->left = NULL;
if(prev) {
prev->right = root;
prev = root;
} else {
prev = root;
}
root->right = flattenBST(root->right); //Trust
if(head == NULL) {
return root;
}
return head;
}
};
/******************************** JAVA ********************************/
Class Solution {
private Node prev = null;
public Node flattenBST(Node root) {
if (root == null) {
return null;
}
Node head = flattenBST(root.left); // Trust
root.left = null;
if (prev != null) {
prev.right = root;
prev = root;
} else {
prev = root;
}
root.right = flattenBST(root.right); // Trust
if (head == null) {
return root;
}
return head;
}
}

[@pranavsharma7479]

can you explain how it will be O(n^2) for the solution discussed in the video.

[@Sranju23]

Theres'a another variation of this qsn on Leetcode:
Medium, Premium == 114. Flatten Binary Tree to Linked List (not BST but BT)
Great video! Thank you :)

[@reppee4392]

I love the way to build the intiution 💖 Here's some modification :
T.C is actually O(n log n) not n^2 bcz at max the while loop will traverse to the max depth of BST which is log(N) .... :).............but i've solved it with O(N) time using 2 pointer and recursion
here's the code :
Node *flattenBST(Node *root)
{
return f(root,NULL);
}
Node * f(Node * root,Node * prev){
if(!root) return NULL;
Node * left = f(root->left,root);
Node * right = f(root->right,prev);

if(prev and prev->left!=NULL){
root->right = prev;
prev->left=NULL;
if(!left) return root;
return left;
}
root->right = right;
if(!left) return root;
return left;
}

[@codestorywithMIK]

Thank you so much.
Yes you are correct, I have added the correction in the caption and also in the Pinned Comment of this video.

[@ChiragWadwa]

maximum depth of n hi hoga na ...so isnt it O(n2)

[@reppee4392]

yeah n hi hoga depth but ye binary search tree hey na so max depth can be log(n) that's why it'll be o(nlog(n))
@Wadwa

[@ashutoshpandey1639]

cover this problem using morris traversal

[@EngineeringSprits]

bro you are on next level mtlb feel krra diya code

[@dhruvkashyap6617]

love the way you teach

[@DevOpskagyaan]

Thank you for bringing the videos daily ❤️

[@snehajajodia75]

Damn good mik!! I am your big fan❤

[@thefinalfit]

I now believe Recursion is indeed magic.

[@oqant0424]

11/18 done [28.5.24] ✅✅

[@dayashankarlakhotia4943]

class Solution {
private Node prev;
private Node head;
public Node treeToDoublyList(Node root){
if(root==null) return null;
prev=null;
head=null;
solve(root);
prev.right=head;
head.left=prev;
return head;
}
private void solve(Node root){
if(root==null) return

[@dayashankarlakhotia4943]

private void solve(Node root){
if(root ==null) return;
solve(root.left)
if(prev!=null){
prev.right=root;
root.left =prev;
}else{
head=root;
}
prev=root;
solve(root.right);
}
}
🎉❤

[@gauravbanerjee2898]

Thanks a lot bhaiya ❤❤. Can you please make a video on Diameter of a Binary Tree, there are several videos out there but every video is confusing

[@codestorywithMIK]

yes yes , I will cover those too.
Also, please see my Pinned comment ❣

[@rohitsonar8858]

Can we use morris traversal to solve this question

[@ssboy5862]

Sir apse doubt kaise puch skte hai

[@DeepakSingh-fd2ix]

hum first hai

[@codestorywithMIK]

Thank you 🙂
Also, please see my Pinned comment ❣

[@wearevacationuncoverers]

Thanks a lot mik

[@nish0798]

//User function Template for Java
class Solution {
public Node flattenBST(Node root) {

if(root==null)
{
return null;
}
if(root.left==null&&root.right==null)
{
return root;
}
Node head1=flattenBST(root.left);
root.left=null;
Node temp=head1;
while(temp!=null && temp.right!=null)
{
temp=temp.right;
}
temp.right=root;
root.right=flattenBST(root.right);
return head1;
}
}
@codestorywithMIK bro can you tell me why this code fails I wrote this i mean it should pass but I dont know why it fails please check

[@nish0798]

No problem bro I figured out WHEN ARE U BRINGING BACKTRACKING CONCEPTS PLEASE COVER THOSE MINUTE DETAILS i MENTIONED UNDER COMMENT SECTION OF ONE OF YOUR VIDEOS IF U DONT REMEMBER I CAN REMIND YOU AGAIN WHAT I AM TALKING ABOUT

[@suhashs1487]

This above code idea is not suitable for solving bst flatten in leetcode