Examine the following binary search tree and answer the questions in Exercises 3

Question

Examine the following binary search tree and answer the questions in Exercises 37-40. The numbers on the nodes are labels so that we can talk about the nodes; they are not key values within the nodes. If an item is to be inserted whose key value is less than the key value in node 1 but greater than the key value in node 5, where would it be inserted? If node 1 is to be deleted, the value in which node could be used to replace it? 42751683 is a traversal of the tree in which order? 1 2 4 5 7 3 6 8 is a traversal of the tree in which order?

Explanation / Answer

37. If an item is to be inserted whose key value is less than the key value in node 1, but greater than the key value in node 5, where would it be inserted?

The binary search tree rule is that, at every node, all the nodes left children should be less than the node, and all the nodes right children should be greater than the node. And when you are supposed to insert an element, you have to traverse through a path from root to an empty node to insert following the same rule. So, if you want to insert an element that is less than key value in node 1, you should go to the left of 1. As the value is greater than 5, it should obviously be greater than 2, so go to the right of 2. As it is greater than 5, and the right node of 5 is empty, now, the new node should be attached to the right of 5.

38. If node 1 is to be deleted, the value in which node could be used to replace it?

When you want to delete a node in the binary search tree, there could be 3 different possibilities:

1. A node with no child: It can simply be removed.

2. A node with single child: This node can be removed by simply replacing the link in its parent with the link to its only child.

3. A node with two children: First let us choose the minimum element in the right subtree. In our case this is at node 6. Replace the node to be removed, i.e., 1 with this minimum value, so, now 6 will be the new root. And now we can remove the node 6 at the bottom, as this is having a single child, obviously this will be connected to the left of 3.

39. The Inorder traversal of the tree is: 4, 2, 7, 5, 1, 6, 8, 3.

40. The postorder traversal of the tree is: 1, 2, 4, 5, 7, 3, 6, 8.

Related Questions

Navigate

• Browse (All)
• Browse E
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.