关于二叉搜索树最小高度插入序列的疑问（以[1,2,3,4]为例）

Great catch! You're absolutely right that the sequences you mentioned (1324, 1342, 4213, 4231) do produce BSTs with the smallest possible height (if we define height as the number of edges from the root to the farthest leaf, that height is 2). The reason they're missing from your textbook's answer is almost certainly a stricter definition of "minimum-height BST" being used—one that requires the tree to be balanced (a complete binary tree-like structure) rather than just having the smallest possible height number.

Let's break down the trees your sequences generate, and compare them to the balanced minimum-height BSTs your textbook is likely referencing:

1. Tree from sequence 1324 #

1
     \
      3
     / \
    2   4

While this tree's height is indeed 2, the root's left subtree is empty (height 0) and its right subtree has a height of 2. That's a height difference of 2 between the root's subtrees, which violates the balance condition of a "properly balanced" BST (like an AVL tree, where subtree height differences must be ≤1).

In contrast, a textbook-approved minimum-height sequence like 2134 produces this balanced tree:

2
   / \
  1   3
       \
        4

Here, the maximum height difference between any node's subtrees is 1, making it a balanced BST while still maintaining the minimum height of 2.

2. Tree from sequence 4213 #

4
   /
  2
 / \
1   3

This is the mirror case: the root's right subtree is empty, and the left subtree has a height of 2. Again, the height difference of 2 means it's not a balanced BST, even though its overall height is minimal.

Key Takeaway #

Your textbook's "minimum-height insertion sequences" are probably referring to sequences that produce balanced minimum-height BSTs (with subtree height differences ≤1), not just any BST that happens to have the smallest possible height. If the definition was only about height, your sequences would be valid—but the stricter balance requirement excludes them.

It's also worth double-checking your textbook's exact definition of "minimum-height BST" to confirm this is the case!

内容的提问来源于stack exchange，提问作者Meg