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 has a time complexity of $O(h)$, where $h$ is the height of the tree. It identifies the node immediately following a given node in an in-order traversal.
- TREE-MAXIMUM: This operation also has a time complexity of $O(h)$. It requires traversing the rightmost path of the tree to locate the node containing the maximum value.
- INORDER-WALK: This operation iterates through all nodes in the tree, printing them in in-order sequence. Its time complexity is $O(n)$, where $n$ represents the total number of nodes.
- TREE-MINIMUM: This operation, like TREE-MAXIMUM, is $O(h)$. It involves traversing the leftmost path to find the node with the minimum value.

Step 2: Conclusion.
INORDER-WALK is the procedure with a distinct running time complexity of $O(n)$. The other procedures (TREE-SUCCESSOR, TREE-MAXIMUM, and TREE-MINIMUM) all have $O(h)$ complexity.