The number of ways in which the numbers 1, 2, 3, 4, 5, 6, 7 can be inserted in…

Key insight: to get height 6 with 7 nodes the binary search tree must be a single chain (every node has at most one child).

• When inserting keys one by one into a BST, a newly inserted key becomes a leaf. To keep the tree a chain at each insertion the new key must attach to one of the two ends of the current chain.

• For the set {1,2,3,4,5,6,7}, after choosing the first inserted key, every subsequent insertion must be either the smallest remaining key or the largest remaining key; otherwise the insertion would create a branching and reduce the maximum possible height.

• There are 6 insertions after the first, and at each insertion there are 2 valid choices (current minimum or current maximum). Thus the total number of valid insertion orders is 2^6 = 64.

Brief check: for 3 keys this reasoning gives 2^2 = 4 permutations that produce a chain, which matches direct enumeration.

Answer: 64