无左子树且为父节点左子节点的BST节点中序前驱疑问

这种情况下，节点𝑥的中序前驱不一定是祖父节点，可能是更远的祖先节点，核心判断逻辑是：

当𝑥无左子树且是父节点的左子节点时，需要沿着父节点向上遍历祖先链，直到找到第一个满足「该节点是其自身父节点的右子节点」的祖先节点（记为A），那么A的父节点就是𝑥的中序前驱；如果遍历到根节点都找不到这样的A，说明𝑥是整棵树的最小节点，不存在中序前驱。

举个具体例子：

100
         /   \
        40    120
       / \
      20  60
         / \
        50  70
       /
      45

节点𝑥=45无左子树，且是父节点50的左子节点：

• 父节点50大于45，无法作为前驱；
• 向上遍历到祖父节点60，发现60是其父节点40的右子节点；
• 此时60的父节点40小于45，因此40就是𝑥=45的中序前驱，而40是𝑥的曾祖父节点，并非祖父。

再看你提供的例子：

50
        /  \
      30    70
     /  \
   20   40
       /
      35

𝑥=35的父节点40是30的右子节点，因此40的父节点30就是前驱，这时候恰好是祖父节点，但这只是一种特殊情况，不是必然结果。

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