The numbers 1, 2, .... n are inserted in a binary search tree in some order.…

Key idea: the first number inserted becomes the root of the binary search tree.

Let r be the root value (the first inserted number). In a BST, every value greater than r goes into the right subtree, so the number of nodes in the right subtree equals the count of integers greater than r among 1..n, which is n - r.

We are told the right subtree contains p nodes, so n - r = p. Solving gives r = n - p. Therefore the first number inserted must be n - p.

• Step 1: Let r be the root (first inserted number).

• Step 2: Count of nodes in right subtree = number of values > r = n - r.

• Step 3: Set n - r = p and solve to get r = n - p.

Example: If n = 10 and p = 3 then r = 10 - 3 = 7. The numbers 8, 9, 10 (three numbers) are greater than 7 and form the right subtree.