Find all nodes in a BST that are between a given range of values. Then build a l

Question

Find all nodes in a BST that are between a given range of values. Then build a linked list of the values and the list should be in ascending order.

NOTE: the head of the linked list is declared globally in the back end and its initial value is NULL. Just add the nodes to the linked list using head. The printing of the linked list will also be done in the backend. Helper functions can be used.

void RangeSearch(TreeNode *node, char m, char n);

Tree Struct:

Linked list Struct:

For example:

Start range: b

End range: g

so you would find b, c, d, e, f, g

Linked List:

Explanation / Answer

Answer ->

#include<stdio.h>

struct TreeNode
{
   char key;
   TreeNode *left;
   TreeNode *right;
   TreeNode *parent;
};
struct Node{
   char key;
   Node *next;
};
Node *head = NULL;

void addNodesInLinkedList(char key)
{
    struct Node *temp = new struct Node;
    temp->key=key;
    if (head== NULL)
    {
    head=temp;
    head->next=NULL;
    }
    else
    {
    temp->next=head;
    head=temp;
    }
   printf("%c", temp->key );
}
void RangeSearch(TreeNode *node, char m, char n)
{

   if ( NULL == node )
      return;
   if (m < node->key )
     RangeSearch(node->left,m,n);

   if ( m <= node->key && n >= node->key )
     addNodesInLinkedList(node->key);
   
   if ( n > node->key )
     RangeSearch(node->right, m, n);
}

struct TreeNode* newNode(char key)
{
struct TreeNode *temp = new struct TreeNode;
temp->key = key;
temp->left = NULL;
temp->right = NULL;

return temp;
}

int main()
{
struct TreeNode *root = new struct TreeNode;
char startRange = 'b';
char endRange = 'g';
printf("StartRange - %c ",startRange);
printf("EndRange - %c ",endRange);
printf(" Linked List is : ");
root = newNode('g');
root->left = newNode('e');
root->right = newNode('o');
root->left->left = newNode('a');
root->left->right = newNode('f');
root->right->left = newNode('i');
root->left->left->right = newNode('b');
root->left->left->right->right = newNode('c');
root->left->left->right->right->right = newNode('d');

RangeSearch(root,startRange,endRange);

return 0;
}

------------------------------------------------------------------------------------------------------------------------------------------------

OUTPUT -

Related Questions

Navigate

• Browse (All)
• Browse F
• Subjects

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