Удаление частей дерева двоичного поиска

Question

Я пытаюсь решить следующую проблему:

Вернуть корень двоичного дерева поиска t, модифицированного так, чтобы оно содержало только значения <= k. (Используя обычный класс BST, где у нас есть элемент, слева и справа)

def prune(t,k):
    if not t:
        return None
    if k < t.item
        while t.item > k:
            t = t.left
    return t

Я думаю, что я делаю это совершенно неправильно.. Может быть, есть какой-то простой рекурсивный способ сделать это?

Answer 1

Я думаю, что вы хотите что-то вроде:

def prune(t, k):
    if t is None or t.item > k:
        return None
    t.right = prune(t.right, k)
    return t

Это рекурсивно и "подрезает", когда достигнет None узел или узел больше чем k, Поскольку это BST, t.item <= k означает, что все узлы в t.left будет тоже, поэтому мы можем их игнорировать.