12.2 Querying a binary search tree
12.2-1¶
Suppose that we have numbers between $1$ and $1000$ in a binary search tree, and we want to search for the number $363$. Which of the following sequences could not be the sequence of nodes examined?
a. $2, 252, 401, 398, 330, 344, 397, 363$.
b. $924, 220, 911, 244, 898, 258, 362, 363$.
c. $925, 202, 911, 240, 912, 245, 363$.
d. $2, 399, 387, 219, 266, 382, 381, 278, 363$.
e. $935, 278, 347, 621, 299, 392, 358, 363$.
- c. could not be the sequence of nodes explored because we take the left child from the $911$ node, and yet somehow manage to get to the $912$ node which cannot belong the left subtree of $911$ because it is greater.
- e. is also impossible because we take the right subtree on the $347$ node and yet later come across the $299$ node.
12.2-2¶
Write recursive versions of $\text{TREE-MINIMUM}$ and $\text{TREE-MAXIMUM}$.
12.2-3¶
Write the $\text{TREE-PREDECESSOR}$ procedure.
TREE-PREDECESSOR(x)
if x.left != NIL
return TREE-MAXIMUM(x.left)
y = x.p
while y != NIL and x == y.left
x = y
y = y.p
return y
12.2-4¶
Professor Bunyan thinks he has discovered a remarkable property of binary search trees. Suppose that the search for key $k$ in a binary search tree ends up in a leaf. Consider three sets: $A$, the keys to the left of the search path; $B$, the keys on the search path; and $C$, the keys to the right of the search path. Professor Bunyan claims that any three keys $a \in A$, $b \in B$, and $c \in C$ must satisfy $a \le b \le c$. Give a smallest possible counterexample to the professor's claim.
Search for $9$ in this tree. Then $A = \{7\}$, $B = \{5, 8, 9\}$ and $C = \{\}$. So, since $7 > 5$ it breaks professor's claim.
12.2-5¶
Show that if a node in a binary search tree has two children, then its successor has no left child and its predecessor has no right child.
Suppose the node $x$ has two children. Then it's successor is the minimum element of the BST rooted at $x.right$. If it had a left child then it wouldn't be the minimum element. So, it must not have a left child. Similarly, the predecessor must be the maximum element of the left subtree, so cannot have a right child.
12.2-6¶
Consider a binary search tree $T$ whose keys are distinct. Show that if the right subtree of a node $x$ in $T$ is empty and $x$ has a successor $y$, then $y$ is the lowest ancestor of $x$ whose left child is also an ancestor of $x$. (Recall that every node is its own ancestor.)
First we establish that $y$ must be an ancestor of $x$. If $y$ weren't an ancestor of $x$, then let $z$ denote the first common ancestor of $x$ and $y$. By the binary-search-tree property, $x < z < y$, so $y$ cannot be the successor of $x$.
Next observe that $y.left$ must be an ancestor of $x$ because if it weren't, then $y.right$ would be an ancestor of $x$, implying that $x > y$. Finally, suppose that $y$ is not the lowest ancestor of $x$ whose left child is also an ancestor of $x$. Let $z$ denote this lowest ancestor. Then $z$ must be in the left subtree of $y$, which implies $z < y$, contradicting the fact that $y$ is the successor of $x$.
12.2-7¶
An alternative method of performing an inorder tree walk of an $n$-node binary search tree finds the minimum element in the tree by calling $\text{TREE-MINIMUM}$ and then making $n - 1$ calls to $\text{TREE-SUCCESSOR}$. Prove that this algorithm runs in $\Theta(n)$ time.
To show this bound on the runtime, we will show that using this procedure, we traverse each edge twice. This will suffice because the number of edges in a tree is one less than the number of vertices.
Consider a vertex of a BST, say $x$. Then, we have that the edge between $x.p$ and $x$ gets used when successor is called on $x.p$ and gets used again when it is called on the largest element in the subtree rooted at $x$. Since these are the only two times that that edge can be used, apart from the initial finding of tree minimum. We have that the runtime is $O(n)$. We trivially get the runtime is $\Omega(n)$ because that is the size of the output.
12.2-8¶
Prove that no matter what node we start at in a height-$h$ binary search tree, $k$ successive calls to $\text{TREE-SUCCESSOR}$ take $O(k + h)$ time.
Suppose $x$ is the starting node and $y$ is the ending node. The distance between $x$ and $y$ is at most $2h$, and all the edges connecting the $k$ nodes are visited twice, therefore it takes $O(k + h)$ time.
12.2-9¶
Let $T$ be a binary search tree whose keys are distinct, let $x$ be a leaf node, and let $y$ be its parent. Show that $y.key$ is either the smallest key in $T$ larger than $x.key$ or the largest key in $T$ smaller than $x.key$.
- If $x = y.left$, then calling successor on $x$ will result in no iterations of the while loop, and so will return $y$.
- If $x = y.right$, the while loop for calling predecessor (see exercise 3) will be run no times, and so $y$ will be returned.