The goal of this assignment is to complete #8 from the textbook Write a function

Question

The goal of this assignment is to complete #8 from the textbook

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. Use the following bst values along with the included header and template file for your assingment. So create a main.cpp using the files provided and complete the in order traversal and display the results.

bintree.h & bintree.template can be found here : https://www.cs.colorado.edu/~main/chapter10/

Explanation / Answer

I have provided a different approach for this problem. Here we are doing a reverse inorder traversal and updating the head of the linked list everytime we encounter a node. So at the end of the traversal the head ptr will actually be containing the head of the sorted linked list.

#include <iostream>

using namespace std;
struct Node{
int data;
Node*left;
Node*right;
};
struct ListNode{
int data;
ListNode*next;
};

void treeToList(Node *root,ListNode **head){
if(root==NULL){
return ;
}
treeToList(root->right,head);
if(*head==NULL){
(*head)=new ListNode();
(*head)->data=root->data;
(*head)->next=NULL;
}else{
ListNode* temp=new ListNode();
temp->data=root->data;
temp->next=(*head);
(*head)=temp;
}
treeToList(root->left,head);
}
Node *createNode(int data){
Node *temp=new Node();
temp->data=data;
temp->left=NULL;
temp->right=NULL;
return temp;
}
int main()
{
Node *root=createNode(10);
root->left=createNode(7);
root->right=createNode(15);
root->left->left=createNode(4);
root->left->right=createNode(9);
root->left->left->left=createNode(2);
root->right->right=createNode(17);
ListNode*head=NULL;
treeToList(root,&head);
while(head!=NULL){
cout<<head->data<<" ";
head=head->next;
}
  
return 0;
}

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.