Recall that a binary search tree (BST) is a binary tree in which each node stores a “key,” and, for any node u, the key at node u is larger than all keys in u’s left subtree and smaller than all the...

Recall that a binary search tree (BST) is a binary tree in which each node stores a “key,” and, for any node u, the key at node u is larger than all keys in u’s left subtree and smaller than all the keys in u’s right subtree. (See p. 1160.) That is, a BST is either:

1. an empty tree, denoted by null; or

2. a root node x, a left subtree Tℓ where all elements are less than x, and a right subtree Tr , where all elements are greater than x, and Tℓ and Tr are both BSTs.

Prove that the smallest element in a nonempty BST is the bottommost leftmost node—that is, prove that