Question

The following sequence corresponds to the preorder traversal of a binary search
tree 𝑇:
50, 25, 13, 40, 30, 47, 75, 60, 70, 80, 77
The position of the element 60 in the postorder traversal of 𝑇 is ______. (answer in
integer)
Note: The position begins with 1.

Hint:

Reconstruct the BST from the preorder sequence using the rule that in preorder, all left-subtree values come right after the root and are smaller than it, while all right-subtree values are larger; then trace the postorder (Left, Right, Root) sequence and count the position of 60.

Answer 1

Correct Answer: 7

We are given the preorder traversal of a binary search tree \(T\):

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

Step 1: In preorder (Root, Left, Right), the first element is the root, and because \(T\) is a BST, all values smaller than the root appear immediately after it (forming the left subtree's preorder), followed by all values larger than the root (forming the right subtree's preorder).

Root = 50. Values smaller than 50: 25, 13, 40, 30, 47. First value larger than 50 is 75. So:

Left subtree preorder: 25, 13, 40, 30, 47

Right subtree preorder: 75, 60, 70, 80, 77

Step 2: Build the left subtree (rooted at 25). Root = 25. Values less than 25: 13. Values greater than 25: 40, 30, 47. So 13 is the left child of 25, and the right part [40, 30, 47] has root 40, with 30 (less than 40) as its left child and 47 (greater than 40) as its right child.

Step 3: Build the right subtree (rooted at 75). Root = 75. Values less than 75: 60, 70. Values greater than 75: 80, 77. In [60, 70], root is 60 and 70 (greater) becomes its right child (no left child). In [80, 77], root is 80 and 77 (smaller) becomes its left child (no right child). So 60 is the left child of 75 and 80 is the right child of 75.

Step 4: The complete BST rooted at 50:

• 50
  • Left child: 25
    • Left child: 13
    • Right child: 40
      • Left child: 30
      • Right child: 47
  • Right child: 75
    • Left child: 60
      • Right child: 70
    • Right child: 80
      • Left child: 77

Step 5: Perform postorder traversal (Left, Right, Root).

Postorder of the 25-subtree: postorder(13), then postorder(40-subtree) = 30, 47, 40, then visit 25. This gives 13, 30, 47, 40, 25.

Postorder of the 75-subtree: postorder(60-subtree) = 70, 60 (60 has only a right child), then postorder(80-subtree) = 77, 80 (80 has only a left child), then visit 75. This gives 70, 60, 77, 80, 75.

Step 6: Combine as (left subtree postorder), (right subtree postorder), root:

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

Step 7: Number the positions starting 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}\]