Suppose we want to create a binary search tree by inserting the following values in

the given order:

$15,6,18,3,7,17,20,2,4,13,9$

Answer the following questions.

Draw the binary search tree.

Using the BST in question $1,$ show that that the number of nodes examined in searching

for a value in the tree is one plus the number of nodes examined when the value was

first inserted into the tree.

Write algorithms for the following tasks:

a$)$ Find successor of a node in a BST

b$)$ Find predecessor of a node in a BST

c$)$ Count occurrences of a number in a BST

d$)$ Alternative method of performing in$-$order walk in a BST $($Hints: Find minimum

element and then find the successors of the minimum element$)$

Show that if the right sub$-$tree of a node $x$ in the BST of question $1$ 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.$

Let $x$ be a leaf node, and let $y$ be its parent. Using the BST in question $1,$ show

that $y.$key is either the smallest key larger than x$.$key or the largest key smaller

than x$.$key.

Show the resulting trees after we delete $20,7$ and $30$ from the BST in question $1$

$($each deletion is applied on the original tree$).$

Is the operation of deletion "commutative" in the sense that deleting $x$ and then $y$

from a binary search tree leaves the same tree as deleting $y$ and then $x?$ Argue why

it is or give a counterexample.