Question 4

Computer Awareness Trees Medium

In case of Binary search tree which of the following procedure's running time is distinct among all

(A) TREE-SUCCESSOR (finds successor of the given node)
(B) TREE-MAXIMUM (finds the node with maximum value)
(C) INORDER-WALK (prints all elements of a tree in inorder manner)
(D) TREE-MINIMUM (finds the node with minimum value)
View Dynamic Solution & Explanation
Correct Solution: Option C

Step-by-step Solution:

Explanation:

For a Binary Search Tree (BST):

(A) TREE-SUCCESSOR: Finds the successor of a given node.
Its running time is \(O(h)\), where \(h\) is the height of the tree.

(B) TREE-MAXIMUM: Finds the maximum element by traversing right children.
Its running time is \(O(h)\).

(D) TREE-MINIMUM: Finds the minimum element by traversing left children.
Its running time is \(O(h)\).

(C) INORDER-WALK: Prints all elements of the tree in sorted (inorder) manner.
This must visit every node exactly once.
Its running time is \(\Theta(n)\), where \(n\) is the number of nodes.

Thus, among all given operations, INORDER-WALK has a distinct running time \(\Theta(n)\), while others run in \(O(h)\).

\[ \therefore \;\; \text{Correct answer is (C).} \]