Question

The following sequence corresponds to the preorder traversal of a binary search tree \(T\):

50, 25, 13, 40, 30, 47, 75, 60, 70, 80, 77

The position of the element 60 in the postorder traversal of \(T\) is ______.

Note: The position begins with 1.

Hint:

Rebuild the BST by inserting the given sequence one value at a time using standard BST insertion rules, then read off the postorder traversal (left, right, root).

Answer 1

Correct Answer: 7

Step 1 (Alternate method - subtree-size counting instead of listing the full traversal): Build the same BST as above (root 50, left subtree rooted at 25 with 5 nodes: 25, 13, 40, 30, 47; right subtree rooted at 75).

Step 2: In postorder, the entire left subtree of the root is fully visited before anything in the right subtree, and the root itself is visited last of all. Since 60 lies in the right subtree (rooted at 75), all 5 nodes of the left subtree occupy postorder positions 1 through 5.

Step 3: Within the right subtree rooted at 75, postorder visits the left child's subtree first, then the right child's subtree, then 75 itself. 60 is the left child of 75, so we now look inside the subtree rooted at 60.

Step 4: The subtree rooted at 60 has no left child and one right child, 70 (a leaf). Its postorder is: left (empty, 0 nodes), right (70, 1 node), then the root 60. So within this subtree, 70 is visited first, then 60.

Step 5 (Compute the position by adding sizes): Position of 60 = (size of root's left subtree) + (size of 60's own right subtree) + 1 (for 60 itself) = 5 + 1 + 1 = 7.

\[ \boxed{7} \]