Consider the partial implementation of a Binary Search Tree class. For simplicity, each Node stores only the key. Add a public member function to class BST that returns the smallest value in the tree.

template

class Node {

T key;

Node *left, *right, *parent;

};

template

class BST {

private:

Node root;

public:

Node *Search(const T &key) { Node *cur = root; while (cur != nullptr) if (key == cur->key) return cur; // Found else if (key < cur->key) cur = cur->left; else cur = cur->right; return nullptr; // Not found }

T getSmallest() {

// YOUR CODE GOES HERE

}

};