Skip to content

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}$.

1
2
3
4
TREE-MINIMUM(x)
    if x.left != NIL
        return TREE-MINIMUM(x.left)
    else return x
1
2
3
4
TREE-MAXIMUM(x)
    if x.right != NIL
        return TREE-MAXIMUM(x.right)
    else return x

12.2-3

Write the $\text{TREE-PREDECESSOR}$ procedure.

1
2
3
4
5
6
7
8
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.

Let $x$ be a node with two children. In an inorder tree walk, the nodes in $x$'s left subtree immediately precede $x$ and the nodes in $x$'s right subtree immediately follow $x$. Thus, $x$'s predecessor is in its left subtree, and its successor is in its right subtree.

Let $s$ be $x$'s successor. Then s cannot have a left child, for a left child of $s$ would come between $x$ and $s$ in the inorder walk. (It's after $x$ because it's in $x$'s right subtree, and it's before s because it's in $s$'s left subtree.) If any node were to come between $x$ and $s$ in an inorder walk, then s would not be $x$'s successor, as we had supposed.

Symmetrically, $x$'s predecessor has no 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 if $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.

Note that a call to $\text{TREE-MINIMUM}$ followed by $n - 1$ calls to $\text{TREE-SUCCESSOR}$ performs exactly the same inorder walk of the tree as does the procedure $\text{INORDER-TREE-WALK}$. $\text{INORDER-TREE-WALK}$ prints the $\text{TREE-MINIMUM}$ first, and by

definition, the $\text{TREE-SUCCESSOR}$ of a node is the next node in the sorted order determined by an inorder tree walk.

This algorithm runs in $\Theta(n)$ time because:

  • It requires $O(n)$ time to do the n procedure calls.
  • It traverses each of the $n - 1$ tree edges at most twice, which takes $O(n)$ time.

To see that each edge is traversed at most twice (once going down the tree and once going up), consider the edge between any node $u$ and either of its children, node $v$. By starting at the root, we must traverse $(u, v)$ downward from $u$ to $v$, before traversing it upward from $v$ to $u$. The only time the tree is traversed downward is in code of $\text{TREE-MINIMUM}$, and the only time the tree is traversed upward is in code of $\text{TREE-SUCCESSOR}$ when we look for the successor of a node that has no right subtree.

Suppose that $v$ is $u$'s left child.

  • Before printing $u$, we must print all the nodes in its left subtree, which is rooted at $v$, guaranteeing the downward traversal of edge $(u, v)$.
  • After all nodes in $u$'s left subtree are printed, $u$ must be printed next. Procedure $\text{TREE-SUCCESSOR}$ traverses an upward path to $u$ from the maximum element (which has no right subtree) in the subtree rooted at $v$. This path clearly includes edge $(u, v)$, and since all nodes in $u$'s left subtree are printed, edge $(u, v)$ is never traversed again.

Now suppose that $v$ is $u$'s right child.

  • After $u$ is printed, $\text{TREE-SUCCESSOR}(u)$ is called. To get to the minimum element in $u$'s right subtree (whose root is $v$), the edge $(u, v)$ must be traversed downward.
  • After all values in $u$'s right subtree are printed, $\text{TREE-SUCCESSOR}$ is called on the maximum element (again, which has no right subtree) in the subtree rooted at $v$. $\text{TREE-SUCCESSOR}$ traverses a path up the tree to an element after $u$, since $u$ was already printed. Edge $(u, v)$ must be traversed upward on this path, and since all nodes in $u$'s right subtree have been printed, edge $(u, v)$ is never traversed again.

Hence, no edge is traversed twice in the same direction.

Therefore, this algorithm runs in $\Theta(n)$ time.

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.