Binary Tree - 72: Convert Binary Tree to Doubly Linked List | Convert BST to DLL

Solution:
- We traverse the binary tree in inorder manner
- We take a global variable 'prev' & 'headOfList'
- Now whenever we're traversing any node, for 1st node after null, we assign headOfList to that node
- After each iteration we update the prev to current node

Time Complexity: O(n)
Space Complexity: O(1)

Do Watch video for more info

CHECK OUT CODING SIMPLIFIED

★☆★ VIEW THE BLOG POST: ★☆★

I started my YouTube channel, Coding Simplified, during Dec of 2015.
Since then, I've published over 200+ videos.

★☆★ SUBSCRIBE TO ME ON YOUTUBE: ★☆★

★☆★ Send us mail at: ★☆★

[_VIVEKNANDAN]

It's the best explanation of this question on Internet

[arijitdassharma]

that's a pretty good explanation . Thanks

[selvalooks]

Super !!! understood, thanks, clearly explained !!!!

[jeevanreddy]

so after converting binary tree to doubly linked list how come a person know which node is root node

[amitkumar]

Nice!! Crisp & Clear explanation. Thanks 😊

[noobninja]

Thanks a lot sir, Perfect explanation

[kamlendratripathi]

where are you printing the data or output i have typed the same code output is balnk

[tonyriddle]

mine is not passing all the cases... could you help

Node* head;
// Node* prev;
void viaInorder(Node* root){
if(root == nullptr) return;

static Node* prev = nullptr;

viaInorder(root->left);

if(prev == nullptr){
head = root;
}
else{
root->left = prev;
prev->right = root;
}
prev = root;

viaInorder(root->right);
}

Node * bToDLL(Node *root)
{

if(root == nullptr) return root;
head = nullptr;
viaInorder(root);

return head;
}

[yashpreetbathla]

Omg you explain so well dude awseome thanks :)))

[nitunsingh]

C++ Code for this one:
class Solution
{
public:
//Function to convert binary tree to doubly linked list and return it.

void helper(Node* root, Node*&head, Node*&prev){
if(root==NULL){
return;
}
helper(root->left, head, prev);
if(prev==NULL){
head=root;
prev=root;
}else{
prev->right=root;
root->left=prev;
prev=root;

}
helper(root->right, head, prev);
}
Node * bToDLL(Node *root)
{
// your code here
if(root==NULL){
return NULL;
}
Node* newhead=NULL;
Node* prev=NULL;
helper(root, newhead, prev);
return newhead;
}
};

[queeengirl]

One doubt sir.. At 5.55 we assign prev=node why we assign prev node to node

[abhiram]

can we convert binary tree to DLL using postorder?

[mishalraj]

Dude u explained it very well and this video deserves more views.

[AnkitKumar-mfvg]

Explanation was good
I think space complexity is O(logn) because it would be the height of tree
Correct me If I am wrong

[saumyarajsinhzala]

Even if consider the recursive stack space, wont the space complexity be log(n) (i.e depth) for binary search tree?

[abhijeetv]

How to do binary tree to circular doubly linked list??

[ChandraShekhar-bycd]

Thanks a lot for such a detailed and simplified explanation. Plsease upload more video on leetcode Medium problems.

[yoyo]

after prev.right = node we write prev=node, so instead of prev=node can it be prev=prev.right; ?

[shubhamchourasia]

Any online coding site where I can test the code?

[unezkazi]

When you called the functions recursively, would the variables Node* previous and Node* headofDLL be created again and again with NULL? Should we declare them globally?