Question

Write a function that takes a binary search tree as input and produces a linked list of the entries, with the entries sorted

(smallest entries at the front of the list and largest entries at the back). *Hint: use in-order traversal.*

C++

there is no any structure

Answer 1

#include<iostream>
using namespace std;
//assuming
//structure/node for BST IS
class node_bst
{
   public:
   int value;
   node_bst *left,*right;
   //constructor
   node_bst(int v)
   {
       value=v;
       left=right=NULL;
   }
};

//structure for linked list node
class lnode
{
   public:
   int value;
   lnode *next;
   //constructor
   lnode(int v)
   {
       value=v;
       next=NULL;  
   }
};

//class for linkedlist
class linked_list
{
   public:
   lnode *head,*tail;
   //constructor
   linked_list()
   {
       head=tail=NULL;  
   }  
   //method to add a node to linked list at tail
   void add(int v)
   {
       lnode *n = new lnode(v);//creating new node
       if(head==NULL)//if list is empty
       {
           head=tail=n;  
       }
       else
       {
           //adding at tail
           tail->next=n;
           tail=n;
       }
   }
  
  
   //method to create linked list with sorted entries from given binarysearchtree
   //by traversing in inorder
   void create_linked_list(node_bst *r)
   {
       if(r==NULL)return;
       create_linked_list(r->left);
       add(r->value);//adding to linked list
       create_linked_list(r->right);
      
   }
  
   //method to print linked list
   void print()
   {
       lnode *t=head;
       while(t!=NULL)
       {
           cout<<t->value<<" ";
           t=t->next;  
       }
       cout<<endl;
   }
};

int main()
{
   //now testing abovemethod
   //creating bst
   node_bst *b = new node_bst(5);
   b->left=new node_bst(3);
   b->right=new node_bst(7);
   b->left->right = new node_bst(4);
   b->right->left= new node_bst(6);
  
  
   //now creating sorted linked list from bst, using implemented method
   linked_list *l = new linked_list();
   l->create_linked_list(b);
   //now printing linked list
   l->print();
}

output:

3 4 5 6 7

Process exited normally.
Press any key to continue . . .

//PLS give a thumbs up if you find this helpful, it helps me alot, thanks.

//if you have any doubts, ask me in the comments