Вернуть родительский узел, который находится точно под корнем

Question

У меня есть общее дерево, которое может выглядеть следующим образом:

Я хочу написать функцию MyFunc (tree, tree_element), который вернет родителя элемента.Но не непосредственный родитель, а родитель, который находится ровно на один уровень ниже корня.В случае прикрепленного дерева:

MyFunc(tree,'Dasani')

вернет 'Coke', а:

MyFunc(tree,'Zero Sugar')

вернет 'Pepsi'

Я смог написать двафункции.Первый возвращает непосредственного родителя:

class tree:
    def __init__(self, key):
            self.data = key
            self.left = None
            self.right = None

    def parent_search(self, root, child_node):
        if  root :
            if root.left and root.left.data== child_node:
                return root.data
            if root.right and root.right.data== child_node:
                return root.data
            elif root:
                return self.parent_search(root.left, child_node) or self.parent_search(root.right, child_node)

root = tree('Beverage') 
root.left = tree('Pepsi') 
root.right = tree('Coke') 
root.left.left = tree('Zero Sugar') 
root.left.right = tree('Cherry Pepsi') 
root.right.left = tree('Sport Drinks')
root.right.left.left = tree('Powerade')
root.right.left.right = tree('Dasani')
root.right.left.left.left = tree('Powerade w/Sugar')

print(root.parent_search(root,'Dasani'))

Второй возвращает весь путь вплоть до корня:

def printAncestors(root, target): 

    if root == None: 
        return False 

    if root.data == target: 
        return True 

    if (printAncestors(root.left, target) or 
        printAncestors(root.right, target)): 
        print root.data, 
        return True

     return False
printAncestors(root, 'Dasani')

Однако мне нужно что-то промежуточное, что вернет только одинэлемент, который находится ровно на один уровень ниже корня.Я могу рассчитать высоту дерева от рассматриваемого листа до корня.Тогда я думал вернуть элемент, который имеет высоту 1 над листом, но не уверен, что это правильный подход.

Answer 1

Один из способов сделать это - передать путь к корню на каждый уровень рекурсии, а затем вернуть весь путь, после чего вы можете извлечь любую часть нужного вам пути, например:

Код:

def parent_search(self, child_node, path_so_far=()):
    path_so_far += self.data,
    if (self.left and self.left.data == child_node or
            self.right and self.right.data == child_node):
        return path_so_far
    return (
        self.left and self.left.parent_search(child_node, path_so_far) or
        self.right and self.right.parent_search(child_node, path_so_far)
    )

Код теста:

class Tree:
    def __init__(self, key):
        self.data = key
        self.left = None
        self.right = None

    def parent_search(self, child_node, path_so_far=()):
        path_so_far += self.data,
        if (self.left and self.left.data == child_node or
                self.right and self.right.data == child_node):
            return path_so_far
        return (
            self.left and self.left.parent_search(child_node, path_so_far) or
            self.right and self.right.parent_search(child_node, path_so_far)
        )


root = Tree('Beverage')
root.left = Tree('Pepsi')
root.right = Tree('Coke')
root.left.left = Tree('Zero Sugar')
root.left.right = Tree('Cherry Pepsi')
root.right.left = Tree('Sport Drinks')
root.right.left.left = Tree('Powerade')
root.right.left.right = Tree('Dasani')
root.right.left.left.left = Tree('Powerade w/Sugar')

print(root.parent_search('Dasani'))
print(root.parent_search('Dasani')[1])

Результаты:

('Beverage', 'Coke', 'Sport Drinks')
Coke