Question

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)

Hint:

In binary search trees, tree traversal operations like **INORDER-WALK** require visiting all nodes, whereas finding successors, minimum, and maximum require only traversing the height of the tree.

Answer 1

The Correct Option is C

Step 1: Analyze the procedures.
- **TREE-SUCCESSOR**: This operation is **$O(h)$** where $h$ is the height of the tree. It involves finding the node that follows a given node in the in-order traversal.
- **TREE-MAXIMUM**: This operation is **$O(h)$**, as it involves traversing down the rightmost path of the tree to find the node with the maximum value.
- **INORDER-WALK**: This operation visits each node of the tree and prints them in in-order sequence, resulting in a time complexity of **$O(n)$**, where $n$ is the number of nodes in the tree.
- **TREE-MINIMUM**: This operation is **$O(h)$**, similar to **TREE-MAXIMUM**, as it involves traversing the leftmost path to find the node with the minimum value.

Step 2: Conclusion.
The procedure that is distinct in terms of running time is **INORDER-WALK**, as its time complexity is **$O(n)$** while the others have **$O(h)$** complexity.