# Problems about binary search tree in Java

Questions:

a. Consider the following binary search tree: (Please see the figure in attached problem file)

i. What tree results after you insert the nodes 44, 48, 32, 36, 38, and 49 in that order? You only need to show the final result.

ii. Given the original tree, what tree results when you delete the node 43 and then node 50? (Note: there may be more than one correct answer, but please choose only one).

a. If you delete an item from a binary search tree and then immediately insert it back into the tree, will you always end up with the same tree? Briefly justify your answer.

b. Suppose that we have a set of unique numbers between 1 and 1000 in a binary search tree and want to search for the number 363. Which of the following sequences could not be the sequence of nodes examined? Only explain the invalid cases (no need to explain the others).

i. 2, 252, 401, 398, 330, 344, 397, 363

ii. 924, 220, 911, 244, 898, 258, 362, 363

iii. 925, 202, 911, 240, 912, 245, 363

iv. 2, 399, 387, 219, 266, 382, 381, 278, 363

v. 935, 278, 347, 621, 299, 392, 358, 363

c.Write the following method which tests if a BinaryTree is a binary search tree. Assume this method exists in the BinaryTree class. Note: Empty binary trees should also be considered to be binary search trees.

public boolean isBinarySearchTree()

// post: returns true iff this is a binary search tree

#### Solution Preview

a. Consider the following binary search tree: (Please see the figure in the attached problem file or solution file).

i. What tree results after you insert the nodes 44, 48, 32, 36, 38, and 49 in that order? You only need to show the final result.

Answer:

First observe the original tree, you will find that it has a very nice property:

for each node, the value of its left child (if any) is < the node value, and the value of its right child (if any) is > the node value. To insert a node into the tree, you need to compare the its value with the tree node value (starting from the root): if > tree node value, continue comparing it with tree node's right child, otherwise compare it with tree node's left child. If the left child is NULL, insert the required node as the current node's left child; if the right child is NULL, insert the required node as the current node's right child. For example, to insert node 44, the following comparisons will take place:

 44 > 43 (value of the root), continue comparison with root's right child which has value 50.

 44 < 50, continue comparison with node 50's left child which is null, finish the comparison, and insert node 44 as node 50's left child.

So the final result ...

#### Solution Summary

Problems about binary search tree in Java are resolved.