Code in C++ Please Find all nodes in a BST that are between a given range of val
ID: 3837860 • Letter: C
Question
Code in C++ Please
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.
USE: void RangeSearch(TreeNode *node, char m, char n); to write code
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:
Answer:
Explanation / Answer
struct TreeNode
{
char key;
TreeNode *left;
TreeNode *right;
TreeNode *parent;
};
//Linked list Struct:
struct Node
{
char key;
Node *next;
};
Node *head = NULL;
Node * getLastNode( Node *head ) // find last node in linked list
{
if (!head)
return NULL;
while (head->next != NULL)
{
head = head->next;
}
return head;
}
/*this is in-order traversal of BST*/
void RangeSearch( TreeNode *node, char m, char n )
{
static bool flag = false;
if (node)
{
RangeSearch(node->left, m, n);
if (node->key == m)
{
flag = true; // start adding node into linked list
if (head == NULL)
{
head = new Node();
head->key = m;
head->next = NULL;
}
if(m==n)
flag = false; // if range has only one element
} else if (node->key == n)
{
flag = false; // stop
Node *last = getLastNode(head);
Node *temp = new Node();
temp->key = n;
last->next = temp;
} else if (flag)
{ // if flag is true add to linked list
Node *last = getLastNode(head);
Node *temp = new Node();
temp->key = n;
last->next = temp;
}
RangeSearch(node->right, m, n);
}
}