Code in C++ Please Find all nodes in a BST that are between a given range of val

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);

}

}

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

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