我的二叉搜索树removeLessThan方法存在什么问题？如何修正？

需求说明 #

实现removeLessThan函数，输入BST节点node和目标值value，移除树中所有值小于value的节点，调用方式为：

root = removeLessThan(root, value);

原伪代码 #

removeLessThan(node, value)

    if (node == null)
        return null
    
    if (node.value >= value)
        node.left = removeLessThan(node.left, value)
    
    else if (node.value < value)
        node.left = removeLessThan(node.left, value)
        node.right = removeLessThan(node.right, value)
        node = null
    
    return node

错误原因分析 #

1. 违背BST特性，做了冗余且错误的处理：
   当node.value < value时，根据BST的性质，该节点的整个左子树所有节点值必然都小于当前节点值，也就是全部小于value，直接丢弃左子树即可，不需要递归处理左子树。
2. 节点删除逻辑错误：
   当当前节点值小于value时，该节点需要被删除，但原代码将node设为null后返回，会直接丢失其右子树。实际上，右子树中可能存在值大于等于value的节点，需要递归处理右子树后返回，作为上层节点的子节点。

改进后的伪代码 #

removeLessThan(node, value)

    if (node == null)
        return null
    
    if (node.value < value):
        # 当前节点及左子树都要删除，递归处理右子树并返回
        return removeLessThan(node.right, value)
    else:
        # 当前节点保留，递归清理左子树中小于value的节点
        node.left = removeLessThan(node.left, value)
        return node

逻辑说明 #

• 当节点为空时，直接返回null。
• 如果当前节点值小于value：当前节点和左子树都不符合要求，直接返回处理后的右子树（右子树可能还有需要保留的节点）。
• 如果当前节点值大于等于value：保留当前节点，递归清理其左子树中小于value的节点，右子树无需处理（因为BST右子树值都大于等于当前节点，必然大于等于value）。

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