Prints the k closest nodes to target t in a binary search tree

print_closest.py

# coding: utf-8
class Node:
    def __init__(self, value, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right
    
    def __str__(self):
        return str(self.value)  
        
#Given a binary search tree rooted at “root”, find the k elements whose values are closest to given value “t”

def minimum(root):
    while root.left:
        root = root.left
    return root

def maximum(root):
    while root.right:
        root = root.right
    return root

def successor(root, node):
    if node.right:
        return minimum(node.right)

    suc = None
    while root:
        if node.value < root.value:
            suc = root
            root = root.left
        elif node.value > root.value:
            root = root.right
        else: break
    return suc

def predecessor(root, node):
    if node.left:
        return maximum(node.left)

    pre = None
    while root:
        if node.value < root.value:
            root = root.left
        elif node.value > root.value:
            pre = root
            root = root.right
        else: break
    return pre

def print_closest(root, k, t):
    res = []
    n = root
    while n:
        if t < n.value:
            n = n.left
        elif t > n.value:
            n = n.right
        else: break
    first = second = n
    while k:
        succ = successor(root, first)
        pred = predecessor(root, second)
        if (t - pred.value > succ.value - t):
            res.append(succ)
            first = succ
        elif (t - pred.value <= succ.value - t):
            res.append(pred)
            second = pred
        k -= 1

    return res
    
tree1 = Node(35)
tree1.left = Node(28)
tree1.left.left = Node(2)
tree1.left.left.left = Node(1)
tree1.left.right = Node(29)
tree1.right = Node(45)
tree1.right.left = Node(41)
tree1.right.left.right = Node(43)
tree1.right.right = Node(55)

closest = print_closest(tree1, 3, 29)
for n in closest:
    print(n.value)