I’m having trouble wrapping my head around the explanation given in the webinar. The task is to convert the Binary Tree into a Linked List in place. In the solution that is discussed, there has been a use of:
class LinkedList{
public:
node*head;
node*tail;
};
Which is, for every node, we are reassigning the pointers to head and tail. I’m not sure I understand how this task is being done inplace (without extra memory). Please clarify.
The only space used will be of recursion stack and no other space will be used
No,
So the case is, For each node, besides having a Node class, we’re also having a LinkedList class.
How is in place then? We are having an auxiliary container (the LinkedList class) to store the head and tail for us, Isnt it?
Can you share the whole code?
This is the link posted from the webinar.
The relevant part is:
class node{
public:
int data;
node*left;
node*right;
node(int d){
data = d;
left = NULL;
right = NULL;
}
};
class LinkedList{
public:
node*head;
node*tail;
};
LinkedList tree2LL(node*root){
LinkedList l;
if(root==NULL){
l.head = l.tail = NULL;
return l;
}
else if(root->left==NULL && root->right==NULL){
l.head = root;
l.tail = root;
}
else if(root->left!=NULL && root->right==NULL){
LinkedList leftLL = tree2LL(root->left);
leftLL.tail->right = root;
l.head = leftLL.head;
l.tail = root;
}
else if(root->left==NULL && root->right!=NULL){
LinkedList rightLL = tree2LL(root->right);
root->right = rightLL.head;
l.head = root;
l.tail = rightLL.tail;
}
else{
LinkedList leftLL = tree2LL(root->left);
LinkedList rightLL = tree2LL(root->right);
leftLL.tail->right = root;
root->right = rightLL.head;
l.head = leftLL.head;
l.tail = rightLL.tail;
}
return l;
}
int main(){
node*root = NULL;
LinkedList l = tree2LL(root);
node*temp = l.head;
while(temp!=NULL){
cout<<temp->data<<"->";
temp = temp->right;
}
cout<<"NULL"<<endl;
return 0;
}The auxiliary space used is not that much considerable as an in place algorithm can use a small amount of extra storage space is allowed for auxiliary variables. If the space used was of higher order then we would not have considered this inplace
The auxillary linkedlist stores only the pointers so it is not a big memory usage
Thanks for your reply.
Actually, The auxiliary space stores the approximately the same amount of memory as the Node class. Like the node class, this also has 2 pointers. Also note that this is for each node (Please confirm this point). If we compare:
Node class: 4 (int) + Node*(8) + Node*(8) = 20 bytes
Linked List class: Node*(16) + Node*(8) = 16 bytes
Thus 80% extra space per node. As far as I know, Inplace should be without using extra memory. Even if memory is used, it should be negligible. The memory usage here is non-negligible. Saving Node* in a stack or any other 1D data structure perhaps would have been much more space optimised that this. Each node* would take 8 bytes versus LinkedList class which takes 16 bytes.
Is there a better method than this? I saw a few other methods and they seem to be without this overhead requirement.
I also saw a few other questions where instead of inorder, the requirement was to convert the Binary tree into Linked list in Preorder and level order manner
Can we extend this approach for these questions too?
When we talk about space we don’t count the bytes and is measured using big-oh notation, here we are using recursion which will take O(H) space [The max depth ] of the tree.
If you use stack/queue just to store the node pointers then still it would be O(N) to store the pointers of all the nodes.
Clearly O(H)<= O(N) as height of the tree would be lesser than N unless it is skewed tree. So the approach discussed should be optimal.
Yes, that does make sense. Thank you!