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

Alternative approach: build the BST using the standard 'min-max bounds' method for constructing a BST from its preorder sequence, then use the iterative two-stack technique to extract the postorder sequence.

Step 1: Construct the tree using bounds. Process 50, 25, 13, 40, 30, 47, 75, 60, 70, 80, 77 with a pointer that only moves forward. Each node is accepted into the current subtree only if it lies inside the allowed range inherited from its ancestors; otherwise control returns up the tree.

50 is the root with range \((-\infty, \infty)\).
25 lies in \((-\infty,50)\), so it becomes the left child of 50.
13 lies in \((-\infty,25)\), so it becomes the left child of 25.
40 lies in \((25,50)\), so it backs out of 13's branch and becomes the right child of 25.
30 lies in \((25,40)\), so it becomes the left child of 40.
47 lies in \((40,50)\), so it becomes the right child of 40.
75 lies in \((50,\infty)\), so it becomes the right child of 50.
60 lies in \((50,75)\), so it becomes the left child of 75.
70 lies in \((60,75)\), so it becomes the right child of 60.
80 lies in \((75,\infty)\), so it becomes the right child of 75.
77 lies in \((75,80)\), so it becomes the left child of 80.

This is exactly the tree you get by inserting the values one at a time into an empty BST, since ordinary BST insertion follows the same bound rule.

Step 2: Read off the structure. 50 has left child 25 and right child 75. 25 has left child 13 and right child 40, where 40 has left child 30 and right child 47. 75 has left child 60 and right child 80, where 60 has only a right child 70, and 80 has only a left child 77.

Step 3: Two-stack postorder. Push root 50 onto stack \(S1\). Repeatedly pop a node from \(S1\), push it onto \(S2\), then push its left child (if any) followed by its right child (if any) onto \(S1\). When \(S1\) is empty, popping everything from \(S2\) gives the postorder sequence.

Carrying this out on the tree produces:
13, 30, 47, 40, 25, 70, 60, 77, 80, 75, 50

Step 4: Locate 60. Counting positions from 1: 13(1), 30(2), 47(3), 40(4), 25(5), 70(6), 60(7), 77(8), 80(9), 75(10), 50(11).

So 60 sits at position \(7\), matching the given range 7 to 7.