Finish the function called BSTSort. Define a helper function that takes the root

ID: 3787975 • Letter: F

Question

Finish the function called BSTSort.

Define a helper function that takes the root pointer and the values array, and copies the values from each tree node into the array. The challenge is knowing “where” to copy each value — i.e. into what array location? One approach is to also pass an integer denoting the “next” available index, which controls where the next value is stored. You can pass this index by reference and update each time you store, or pass a copy in and return the updated value.

// BSTSort: traverses the tree inorder so as to yield the (key, value)
// pairs in sorted order by key. Returns a dynamically-allocated array
// of size N, containing a copy of the value in each tree node. The
// value N can be obtained by calling BSTCount().
//
// NOTE: the caller is responsible for freeing the returning array.
//
BSTValue *BSTSort(BST *tree)
{
BSTValue *values = (BSTValue *)malloc(tree->Count * sizeof(BSTValue));

//
// fill values by traversing tree:
//

// TODO

return values;
}

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

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>

typedef char* BSTKey;
typedef struct BSTValue
{
char *X;
int Y;
} BSTValue;

typedef struct BSTNode
{
BSTKey Key;
BSTValue Value;
struct BSTNode *Left;
struct BSTNode *Right;
} BSTNode;

typedef struct BST
{
BSTNode *Root;
int Count;
} BST;

//
// BSTCreate: dynamically creates and returns an empty
// binary search tree:
//
BST *BSTCreate()
{
BST *tree;

tree = (BST *)malloc(sizeof(BST));
tree->Root = NULL;
tree->Count = 0;

return tree;
}

//
// BSTCompareKeys: compares key1 and key2, returning
// value < 0 if key1 < key2
// 0 if key1 == key2
// value > 0 if key1 > key2
//
int BSTCompareKeys(BSTKey key1, BSTKey key2)
{
if (strcmp(key1, key2) < 0)
return -1;
else if (strcmp(key1, key2) == 0)
return 0;
else
return 1;
}

//
// BSTSearch: searches the binary search tree for a node containing the
// same key. If a match is found, a pointer to the node is returned,
// otherwise NULL is returned.
//
BSTNode *BSTSearch(BST *tree, BSTKey key)
{
BSTNode *cur = tree->Root;

//
// search the tree to see if it contains a matching key:
//
while (cur != NULL)
{
if (BSTCompareKeys(key, cur->Key) == 0) // found!
return cur;
else if (BSTCompareKeys(key, cur->Key) < 0) // smaller, go left:
{
cur = cur->Left;
}
else // larger, go right:
{
cur = cur->Right;
}
}

// if we get here, we fell out of the tree, and didn't find it:
return NULL;
}

//
// BSTSearchDepth: searches the binary search tree for a node containing the
// same key, returning the depth of that node if found. The root node is
// considered depth 0, the next level down is a depth of 1, and so forth.
// If a matching key is not found, the function returns a depth of -1.
//
int BSTSearchDepth(BST *tree, BSTKey key)
{
BSTNode *cur = tree->Root;
int depth = 0;

//
// search the tree to see if it contains a matching key:
//
while (cur != NULL)
{
if (BSTCompareKeys(key, cur->Key) == 0) // found!
return depth;
else if (BSTCompareKeys(key, cur->Key) < 0) // smaller, go left:
{
cur = cur->Left;
}
else // larger, go right:
{
cur = cur->Right;
}

depth++;
}

// if we get here, we fell out of the tree, and didn't find it:
return -1;
}

//
// BSTInsert: inserts the given (key, value) pair into the binary search
// tree. Returns true (non-zero) if the insert was successful, returns
// false (0) if the given key is already in the tree -- in which case the
// given (key, value) pair is not inserted.
//
int BSTInsert(BST *tree, BSTKey key, BSTValue value)
{
BSTNode *prev = NULL;
BSTNode *cur = tree->Root;

//
// first we search the tree to see if it already contains key:
//
while (cur != NULL)
{
if (BSTCompareKeys(key, cur->Key) == 0) // already in tree, failed:
return 0;
else if (BSTCompareKeys(key, cur->Key) < 0) // smaller, go left:
{
prev = cur;
cur = cur->Left;
}
else // larger, go right:
{
prev = cur;
cur = cur->Right;
}
}

//
// If we get here, tree does not contain key, so insert new node
// where we fell out of tree:
//
BSTNode *T = (BSTNode *)malloc(sizeof(BSTNode));
T->Key = key;
T->Value = value;
T->Left = NULL;
T->Right = NULL;

//
// link T where we fell out of tree -- after prev:
//
if (prev == NULL) // tree is empty, insert @ root:
{
tree->Root = T;
}
else if (BSTCompareKeys(key, prev->Key) < 0) // smaller, insert to left:
{
prev->Left = T;
}
else // larger, insert to right:
{
prev->Right = T;
}

tree->Count++;

return 1; // success:
}

//
// BSTPrintInorder: prints the nodes of the given binary search
// tree inorder to the console.
//
// NOTE: "pf" is a print function that must be declared like this
// (though the name "pf" doesn't really matter):
//
// void pf(BSTNode *cur)
// { ...}
//
// When you call, pass pf and then you'll be able to control
// what gets printed when a node is "visited".
//
void _BSTPrintInorder(BSTNode *root, void (*pf)(BSTNode*))
{
if (root == NULL) // base case: empty tree
return;
else // recursive case: non-empty tree
{
_BSTPrintInorder(root->Left, pf);
pf(root);
_BSTPrintInorder(root->Right, pf);
}
}

void BSTPrintInorder(BST *tree, void(*pf)(BSTNode*))
{
printf(">>Inorder: %d node(s) ", tree->Count);

_BSTPrintInorder(tree->Root, pf);

printf(">><< ");
}

//
// BSTPrintPreorder: prints the nodes of the given binary search
// tree pre-order to the console.
//
// NOTE: "pf" is a print function that must be declared like this
// (though the name "pf" doesn't really matter):
//
// void pf(BSTNode *cur)
// { ...}
//
// When you call, pass pf and then you'll be able to control
// what gets printed when a node is "visited".
//
void _BSTPrintPreorder(BSTNode *root, void(*pf)(BSTNode*))
{
if (root == NULL) // base case: empty tree
return;
else // recursive case: non-empty tree
{
pf(root);
_BSTPrintPreorder(root->Left, pf);
_BSTPrintPreorder(root->Right, pf);
}
}

void BSTPrintPreorder(BST *tree, void(*pf)(BSTNode*))
{
printf(">>Preorder: %d node(s) ", tree->Count);

_BSTPrintPreorder(tree->Root, pf);

printf(">><< ");
}

//
// BSTCount: returns # of nodes in the tree.
//
int BSTCount(BST *tree)
{
return tree->Count;
}

//
// BSTSort: traverses the tree inorder so as to yield the (key, value)
// pairs in sorted order by key. Returns a dynamically-allocated array
// of size N, containing a copy of the value in each tree node. The
// value N can be obtained by calling BSTCount().
//
// NOTE: the caller is responsible for freeing the returning array.
//
BSTValue *BSTSort(BST *tree)
{
BSTValue *values = (BSTValue *)malloc(tree->Count * sizeof(BSTValue));

//
// fill values by traversing tree:
//

// TODO

return values;
}

//
// skipRestOfInput:
//
// Inputs and discards the remainder of the current line for the
// given input stream, including the EOL character(s).
//
void skipRestOfInput(FILE *stream)
{
char restOfLine[256];
int rolLength = sizeof(restOfLine) / sizeof(restOfLine[0]);

fgets(restOfLine, rolLength, stream);
}

//
// BuildTree:
//
// Inputs data from keyboard, stores in a BST, and returns tree.
//
BST *BuildTree()
{
char x[64];
int y;
BSTValue value;

BST *tree = BSTCreate();

//
// input:
// Key Value
// Key Value
// ...
// #
//
scanf("%s", x); // first input the netid:

while (x[0] != '#')
{
scanf("%d", &y);
skipRestOfInput(stdin);

//
// store (key, value) into a BST value struct to insert:
//
value.X = (char *)malloc((strlen(x) + 1) * sizeof(char));
strcpy(value.X, x);

value.Y = y;

//
// now that we have (key, value) pair, call BSTInsert to
// copy this (key, value) pair into a new node of the tree:
//
BSTInsert(tree, value.X, value);

scanf("%s", x); // get next netid or #:
}

//
// done, return tree:
//
return tree;
}

int main()
{
BST *tree;

tree = BuildTree();

//
// Sort the data by traversing the tree:
//
BSTValue *values = BSTSort(tree);

//
// output:
//
int N = BSTCount(tree);
int min = values[0].Y;
int max = values[0].Y;
double sum = 0.0;

for (int i = 0; i < N; ++i)
{
sum += values[i].Y;

if (values[i].Y < min)
min = values[i].Y;

if (values[i].Y > max)
max = values[i].Y;
}

printf("**Average: %f ", sum / N);
printf("**Min: %d ", min);
printf("**Max: %d ", max);
printf("**Data: ");

for (int i = 0; i < N; ++i)
{
printf("%s: %d ", values[i].X, values[i].Y);
}

printf("**Done** ");

// done:

free(values);

return 0;
}

Explanation / Answer