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 (Concept): In a preorder traversal (root, left subtree, right subtree) of a BST, the first value is always the root, and inserting the given sequence, in order, into an initially empty BST using the standard rule (go left if smaller, right if greater) reconstructs the exact same tree, because BST insertion order and its preorder traversal always match.

Step 2 (Insert the values one at a time):
Insert 50 -> root = 50
Insert 25 -> 25 < 50, left child of 50
Insert 13 -> 13 < 50 -> 13 < 25, left child of 25
Insert 40 -> 40 < 50 -> 40 > 25, right child of 25
Insert 30 -> 30 < 50 -> 30 > 25 -> 30 < 40, left child of 40
Insert 47 -> 47 < 50 -> 47 > 25 -> 47 > 40, right child of 40
Insert 75 -> 75 > 50, right child of 50
Insert 60 -> 60 > 50 -> 60 < 75, left child of 75
Insert 70 -> 70 > 50 -> 70 < 75 -> 70 > 60, right child of 60
Insert 80 -> 80 > 50 -> 80 > 75, right child of 75
Insert 77 -> 77 > 50 -> 77 > 75 -> 77 < 80, left child of 80

Step 3 (Resulting tree):

50
  L-25
  |  L-13
  |  R-40
  |     L-30
  |     R-47
  R-75
     L-60
     |  R-70
     R-80
        L-77

Step 4 (Postorder = left, right, root):
Left subtree at 25: postorder(13) = 13; postorder(40-subtree) = 30, 47, 40; combined with root 25 -> 13, 30, 47, 40, 25.
Right subtree at 75: postorder(60-subtree, no left child, right child 70) = 70, 60; postorder(80-subtree, left child 77, no right child) = 77, 80; combined with root 75 -> 70, 60, 77, 80, 75.
Full postorder = [13, 30, 47, 40, 25] + [70, 60, 77, 80, 75] + [50] = 13, 30, 47, 40, 25, 70, 60, 77, 80, 75, 50.

Step 5 (Number the positions from 1): 1:13, 2:30, 3:47, 4:40, 5:25, 6:70, 7:60, 8:77, 9:80, 10:75, 11:50. The element 60 is at position 7.

\[ \boxed{7} \]