Problems about binary search tree in Java
Not what you're looking for?
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
Purchase this Solution
Solution Summary
Problems about binary search tree in Java are resolved.
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 ...
Purchase this Solution
Free BrainMass Quizzes
C++ Operators
This quiz tests a student's knowledge about C++ operators.
Basic UNIX commands
Use this quiz to check your knowledge of a few common UNIX commands. The quiz covers some of the most essential UNIX commands and their basic usage. If you can pass this quiz then you are clearly on your way to becoming an effective UNIX command line user.
Inserting and deleting in a linked list
This quiz tests your understanding of how to insert and delete elements in a linked list. Understanding of the use of linked lists, and the related performance aspects, is an important fundamental skill of computer science data structures.
Javscript Basics
Quiz on basics of javascript programming language.
Java loops
This quiz checks your knowledge of for and while loops in Java. For and while loops are essential building blocks for all Java programs. Having a solid understanding of these constructs is critical for success in programming Java.