Question

Which of the following bst operations are o(h) in the worst case, where h is the height of the bst? select all that apply.

(a) deleting an element
(b) finding the height
(c) finding the size (i.e., number of nodes)
(d) pre-order traversal
(e) searching for an element

Answer 1

The BST operations that are O(h) are deleting an element and searching for an element, with finding height also possibly being O(h) if not stored. Finding the size and pre-order traversal are O(n) because they involve visiting every node.

Step-by-step explanation:

The operations of a Binary Search Tree (BST) that are O(h) in the worst case, where h is the height of the BST, are deleting an element (a), searching for an element (e), and potentially finding the height (b) if the height is not updated and stored during tree modifications. However, finding the size of the tree (c) is O(n), not O(h), because it requires visiting every node. Similarly, a pre-order traversal (d) is also O(n) because it visits every node once.