Let T be a binary search tree BST with n keys Select all the

Let T be a binary search tree (BST) with n keys. Select all the statements below which are TRUE.

A: TREE-INSERT, TREE-DELETE, and TREE-SEARCH have the worst-case running time O(n).

B: If T is a perfectly balanced BST (all leaves have the same depth), then the height of all nodes is O(lg n)

C: PREORDER-TREE-WALK(T.root) prints the keys in monotonically increasing order.

D: The height of T is O(n).

Solution

A: Is TRUE, the worst case running time is building a tree of nodes in increasing order or decreasing order it resulting in right skewed or left skewed. So, it takes to insert, delete, search every element in the tree so it takes O(n) time or every operation

example:

B: Is FALSE, Searching in a BST has O(h) worst-case runtime complexity, where h is the height of the tree.

Height can be defined as levels of Bst. Since binary search tree with n nodes has a minimum of log n levels.

So ,it takes at least O(log n) comparisons to find a particular node.

In our question we want to find height for all nodes so total time is O(n logn).

C: Is FALSE, because first it prints root, then left child, after that right child. So, left child always less than root, and right child always greater than root in BST, it gives not a monotonically increasing order.

But in worst case that is right skewed only it gives monotonically increasing order.

D: Is FALSE, as said above (Answer B) time taken to find a height of one node is O(log n) root node that gives entire tree height. That is O(log n) not a O(n).

But in worst case that is right skewed or left skewed it is O(n).