Вертикальный обход порядка в двоичном дереве — интервью Amazon [closed]

Что такое вертикальный обход заказа?

читать здесь — LeetCode

Я написал следующий код в соответствии с логикой, которую я сделал после просмотра некоторого учебника, однако он не выводит правильный результат, что не так с этим кодом?

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

def verticalOrder(root):
    dict1 = {}
    queue = []
    hd = 0
    queue.append(root)
    dict1[hd] = [root.data]


    while(len(queue)>0):
        curr = queue.pop(0)

        if curr.left is not None:
            hd -= 1
            dict1.setdefault(hd,[])
            dict1[hd].append(curr.left.data)

            queue.append(curr.left)
        if curr.right is not None:
            hd += 1
            dict1.setdefault(hd, [])
            dict1[hd].append(curr.right.data)
            queue.append(curr.right)

    return dict1

root = BinaryTree(1)
root.left = BinaryTree(2)
root.right = BinaryTree(3)
root.left.left = BinaryTree(4)
root.left.right = BinaryTree(5)
root.right.left = BinaryTree(6)
root.right.right = BinaryTree(7)
root.right.left.right = BinaryTree(8)
root.right.right.right = BinaryTree(9)

print(verticalOrder(root))

Ожидаемый результат:

Vertical order traversal :- 
4 
2 
1 5 6 
3 8 
7 
9 

Токовый выход:

{0: [1, 3, 5, 7], -1: [2, 4, 6], 1: [8], 2: [9]}

Примечание. Не беспокойтесь о форматировании ожидаемых и текущих результатов!