class Node:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

class BST:
    def __init__(self):
        self.root = None

def insert(self, value):
    # 創(chuàng)建一個新節(jié)點
    new_node = Node(value)
    # 如果樹為空，則將新節(jié)點設(shè)為根節(jié)點
    if self.root is None:
        self.root = new_node
        return
    # 否則從根節(jié)點開始遍歷
    current = self.root
    while True:
        # 如果要插入的值小于當(dāng)前節(jié)點的值，則向左走
        if value < current.value:
            # 如果左子節(jié)點為空，則將新節(jié)點設(shè)為左子節(jié)點
            if current.left is None:
                current.left = new_node
                return
            # 否則繼續(xù)向左走
            else:
                current = current.left
        # 如果要插入的值大于當(dāng)前節(jié)點的值，則向右走
        elif value > current.value:
            # 如果右子節(jié)點為空，則將新節(jié)點設(shè)為右子節(jié)點
            if current.right is None:
                current.right = new_node
                return
            # 否則繼續(xù)向右走
            else:
                current = current.right
        # 如果要插入的值等于當(dāng)前節(jié)點的值，則不做任何操作，并返回
        else:
            return

def search(self, value):
    # 如果樹為空，則返回False
    if self.root is None:
        return False
    # 否則從根節(jié)點開始遍歷
    current = self.root
    while current is not None:
        # 如果要查找的值小于當(dāng)前節(jié)點的值，則向左走
        if value < current.value:
            current = current.left
        # 如果要查找的值大于當(dāng)前節(jié)點的值，則向右走
        elif value > current.value:
            current = current.right
        # 如果要查找的值等于當(dāng)前節(jié)點的值，則返回True
        else:
            return True
    # 如果遍歷完畢還沒有找到，則返回False
    return False

def delete(self, value):
    # 如果樹為空，則返回None
    if self.root is None:
        return None
    # 否則從根節(jié)點開始遍歷
    current = self.root
    parent = None
    while current is not None and current.value != value:
        # 記錄父節(jié)點
        parent = current
        # 如果要刪除的值小于當(dāng)前節(jié)點的值，則向左走
        if value < current.value:
            current = current.left
        # 如果要刪除的值大于當(dāng)前節(jié)點的值，則向右走
        else:
            current = current.right
    # 如果沒有找到要刪除的元素，則返回None
    if current is None:
        return None
    # 定義一個輔助函數(shù)，用來找到一棵樹中最?。ɑ蜃畲螅┰厮诘慕Y(jié)點和其父結(jié)點，參數(shù)是根結(jié)點和一個布爾變量，表示是否尋找最小元素，默認(rèn)為True，如果為False則尋找最大元素
    def find_min_max(node, is_min=True):
        # 初始化最小（或最大）結(jié)點和其父結(jié)點
        min_max = node
        parent = None
        # 如果尋找最小元素，則一直向左走，否則一直向右走
        if is_min:
            while min_max.left is not None:
                parent = min_max
                min_max = min_max.left
        else:
            while min_max.right is not None:
                parent = min_max
                min_max = min_max.right
        # 返回最?。ɑ蜃畲螅┙Y(jié)點和其父結(jié)點
        return min_max, parent
    # 如果當(dāng)前結(jié)點沒有子結(jié)點，則直接刪除該結(jié)點，并返回None
    if current.left is None and current.right is None:
        # 如果是根結(jié)點，則將根結(jié)點設(shè)為None
        if parent is None:
            self.root = None
        # 否則判斷是父結(jié)點的左子結(jié)點還是右子結(jié)點，并將其設(shè)為None
        else:
            if parent.left == current:
                parent.left = None
            else:
                parent.right = None
        return None
    # 如果當(dāng)前結(jié)點只有一個子結(jié)點，則直接用該子結(jié)點替換該結(jié)點，并返回該子結(jié)點
    if current.left is None or current.right is None:
        # 找到該子結(jié)點，可以是左子結(jié)點也可以是右子結(jié)點
        child = current.left if current.left is not None else current.right
        # 如果是根結(jié)點，則將根結(jié)點設(shè)為該子結(jié)點
        if parent is None:
            self.root = child
        # 否則判斷是父結(jié)點的左子結(jié)點還是右子結(jié)點，并將其設(shè)為該子結(jié)點
        else:
            if parent.left == current:
                parent.left = child
            else:
                parent.right = child
        return child
    # 如果當(dāng)前結(jié)點有兩個子結(jié)點，則先在其右子樹中找到最小值（或者在其左子樹中找到最大值），然后用該最?。ɑ蜃畲螅┲堤鎿Q該結(jié)點，并遞歸地在其右（或左）子樹中刪除該最小（或最大）值，并將刪除后的右（或左）子樹設(shè)為該結(jié)點的右（或左）子節(jié)點
    # 這里我們選擇在右子樹中找到最小值，也可以在左子樹中找到最大值，只要保證替換后的結(jié)點滿足二叉搜索樹的性質(zhì)即可
    min_node, min_parent = find_min_max(current.right, is_min=True)
    # 用最小值替換當(dāng)前結(jié)點的值
    current.value = min_node.value
    # 遞歸地在右子樹中刪除最小值，并將刪除后的右子樹設(shè)為當(dāng)前結(jié)點的右子節(jié)點
    current.right = self.delete(min_node.value)
    return current

def pre_order(self, node):
    # 如果結(jié)點為空，則返回
    if node is None:
        return
    # 先訪問根節(jié)點，打印其值
    print(node.value, end=" ")
    # 再訪問左子樹，遞歸調(diào)用前序遍歷函數(shù)
    self.pre_order(node.left)
    # 最后訪問右子樹，遞歸調(diào)用前序遍歷函數(shù)
    self.pre_order(node.right)
def in_order(self, node):
    # 如果結(jié)點為空，則返回
    if node is None:
        return
    # 先訪問左子樹，遞歸調(diào)用中序遍歷函數(shù)
    self.in_order(node.left)
    # 再訪問根節(jié)點，打印其值
    print(node.value, end=" ")
    # 最后訪問右子樹，遞歸調(diào)用中序遍歷函數(shù)
    self.in_order(node.right)
def post_order(self, node):
    # 如果結(jié)點為空，則返回
    if node is None:
        return
    # 先訪問左子樹，遞歸調(diào)用后序遍歷函數(shù)
    self.post_order(node.left)
    # 再訪問右子樹，遞歸調(diào)用后序遍歷函數(shù)
    self.post_order(node.right)
    # 最后訪問根節(jié)點，打印其值
    print(node.value, end=" ")

def height(self, node):
    # 如果結(jié)點為空，則返回0
    if node is None:
        return 0
    # 否則返回左右子樹中較大的高度加1
    return max(self.height(node.left), self.height(node.right)) + 1
def size(self, node):
    # 如果結(jié)點為空，則返回0
    if node is None:
        return 0
    # 否則返回左右子樹的大小之和加1
    return self.size(node.left) + self.size(node.right) + 1
def kth_smallest(self, node, k):
    # 如果結(jié)點為空，則返回None
    if node is None:
        return None
    # 定義一個輔助函數(shù)，用來計算一棵樹中有多少個小于等于給定值的元素，參數(shù)是根結(jié)點和給定值
    def count_less_equal(node, value):
        # 如果結(jié)點為空，則返回0
        if node is None:
            return 0
        # 如果結(jié)點的值小于等于給定值，則返回左子樹的個數(shù)加右子樹中小于等于給定值的個數(shù)加1
        if node.value <= value:
            return count_less_equal(node.left, value) + count_less_equal(node.right, value) + 1
        # 如果結(jié)點的值大于給定值，則返回左子樹中小于等于給定值的個數(shù)
        else:
            return count_less_equal(node.left, value)
    # 計算當(dāng)前結(jié)點左子樹中有多少個元素
    left_count = self.size(node.left)
    # 如果左子樹中有k-1個元素，則當(dāng)前結(jié)點就是第k小元素，返回其值
    if left_count == k - 1:
        return node.value
    # 如果左子樹中有超過k-1個元素，則第k小元素在左子樹中，遞歸調(diào)用函數(shù)在左子樹中查找
    elif left_count > k - 1:
        return self.kth_smallest(node.left, k)
    # 如果左子樹中有少于k-1個元素，則第k小元素在右子樹中，遞歸調(diào)用函數(shù)在右子樹中查找，注意要更新k的值為k-left_count-1，因為已經(jīng)排除了左子樹和當(dāng)前結(jié)點
    else:
        return self.kth_smallest(node.right, k - left_count - 1)
def lowest_common_ancestor(self, node, p, q):
    # 如果結(jié)點為空，則返回None
    if node is None:
        return None
    # 如果結(jié)點的值等于p或q中的任意一個，則返回該結(jié)點，表示找到了其中一個元素
    if node.value == p or node.value == q:
        return node
    # 否則在左右子樹中分別查找p和q，得到兩個結(jié)果
    left_result = self.lowest_common_ancestor(node.left, p, q)
    right_result = self.lowest_common_ancestor(node.right, p, q)
    # 如果兩個結(jié)果都不為空，則表示p和q分別在當(dāng)前結(jié)點的兩側(cè)，那么當(dāng)前結(jié)點就是最近公共祖先，返回該結(jié)點
    if left_result is not None and right_result is not None:
        return node
    # 如果兩個結(jié)果中有一個為空，則表示p和q都在另一個結(jié)果所在的子樹中，那么返回非空的結(jié)果作為最近公共祖先
    if left_result is None:
        return right_result
    else:
        return left_result