Question

1 Binary Search Trees (25 points) Consider the binary tree as shown in Figure 1. 9 5 15 10 17 8 Figure 1: Binary Tree: The letter next to each node (e.g., a, b) denotes the tree node, and the number inside each node is the key. 1.1 Correctness (10 points) Is this binary tree a valid binary search tree? In other words, does it satisfy the binary search tree property? If not, which node(s) violates the binary search tree property, and why? How would you modify the violating node(s) to make the binary tree a valid binary search tree? Hint: You will lose points if your answer includes tree nodes that do NOT violate the binary search tree property. Insertion (5 points) If we insert a node with key 18 into the binary search tree in Figure 1 (or the corrected version if you need to modify the tree node(s) in the first question), how would the binary search tree look like after the insertion? Please draw the binary search tree as in Figure 1.

Answer 1

Answers:

Ans 1.1.:

For a given Binary Tree to be a BInary Search Tree it has to follow all of the following properties:

1. All the keys in the left subtree of root are less than the key in the root.

2. All the keys in the right subtree of root are greater than the key in the root.

3 Left and right subtrees of root are also binary search Trees.

Now, In the given Binary Tree:
The root node a has value 9 and now all other nodes in the left subtree must have value less than 9 but node e has value 10 and thus it violates the 1st rule that we have seen according to which no node in the left subtree should have value greater than that of the root node. Hence, the given binary tree is not a binary search tree due to node e.

For modifying the tree so as to make it a binary search tree we would remove the node e from the left subtree and join it to node c and make it the left child of c.

Here is the Diagram:

DatePage no: Originat- 5 rec Violods the Property of ter modificationi 9 5 (17

1.2:

The Tree after inserting the node with key=18 in the corrected tree will look like below:

dt e. afiea dnserking

1.3:

Deletion of any node b in the binary search tree will be done as follows:

Date: L-L-Page no: nochb with -Key. te fi Inorder Sutc esho of node b Cl dl ヂ Inade elate the noole h uoith key5 cl 3