BST to sorted linked list

#1

in the line 176,why there is return “leftll.tail->right=root” instead we can write “leftll.tail=root”
also in main function how can we write temp->right?

#2

Hi Pradyumn
The purpose of flattening a BST is to form a Linked List using the already present nodes and not create new ones.
As you would recall a Linked List requires a next pointer for each node to point to its next one. Since we are not creating new nodes and using the tree nodes only , we will be using the ‘right’ pointer of the tree nodes as ‘next’ .
Now we need to change the right pointers of all nodes so the tree becomes a Linked List.
When we do a recursive call on the left subtree , we ask it to provide us a Linked List and its head and tail pointer.

We then connect the tail node with the root node - leftll.tail->right=root”
If we skip this step or change it to “leftll.tail=root” , the linking would never be formed. That’s the whole point of this video.
Eventually the root does become the new tail of the Linked List so far . But it can only be part of the linked list if it is connected to the previous tail.

As for printing the final Linked List in the main( )
Just run a simple loop as you would for a normal Linked List , only use right instead of next.

node *temp = head;
while(temp != NULL) {
cout << temp->data << " ";
temp = temp -> right;
}

#3

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.