Question

Insert the following items into an empty binary search tree in order: {30, 40, 23, 58, 48, 26, 11, 13, 8, 20}. Draw the resulting tree.

a. Write the preorder, inorder and postorder traversals of this tree.
b. What is the maximum height of a binary search tree that contains n items? Why?
c. Write the implementation for finding the minimum element in a binary search tree. You may write either a recursive or iterative implementation.
d. Write the implementation for deleting an element in a binary search tree. You must consider all three cases for your implementation

Answer 1

When inserting given numbers into a binary search tree, it results in specific preorder, inorder, and postorder traversals. The maximum height of a binary search tree with n items is n. Implementations for finding the minimum element and deleting an element are provided using both recursive and iterative methods.

Step-by-step explanation:

Binary Search Tree OperationsTo insert the items into an empty binary search tree in order: {30, 40, 23, 58, 48, 26, 11, 13, 8, 20}, the resulting tree, traversals, maximum height, and implementations for finding the minimum element and deleting an element are as follows:

a. Tree Traversals

b. Maximum Height of Binary Search Tree

The maximum height of a binary search tree that contains n items is n, when the items are inserted in such a manner that every node has only one child.

c. Find Minimum Element

Recursive Implementation:

TreeNode* findMin(TreeNode* node) node->left == NULL)
return node;
return findMin(node->left);

Iterative Implementation:

TreeNode* findMin(TreeNode* node) {
while (node->left != NULL) {
node = node->left;
}
return node;
}

d. Delete Element in Binary Search Tree

TreeNode* deleteNode(TreeNode* root, int key) {
if (root == NULL) return root;
if (key < root->data)
root->left = deleteNode(root->left, key);
else if (key > root->data)
root->right = deleteNode(root->right, key);
else {
if (root->left == NULL) {
TreeNode* temp = root->right;
delete root;
return temp;
} else if (root->right == NULL) {
TreeNode* temp = root->left;
delete root;
return temp;
} else {
TreeNode* temp = findMin(root->right);
root->data = temp->data;
root->right = deleteNode(root->right, temp->data);
}
}
return root;
}