Implement getPredecessor method inside BST class, which returns the key associated with the node that goes immediately before the search key according to key order. Your implementation should have worst-case O(h) running time, where h is the height of the tree.

(Java)

/**

* Return key associated with predecessor

*/

public Key getPredecessor(Key key) {

// provide implementation here

throw new UnsupportedOperationException("Not implemented yet!");

}