+ def _parent_path(self, current: Optional[Node], target: Node) -> List[Optional[Node]]:
+ if current is None:
+ return [None]
+ ret: List[Optional[Node]] = [current]
+ if target.value == current.value:
+ return ret
+ elif target.value < current.value:
+ ret.extend(self._parent_path(current.left, target))
+ return ret
+ else:
+ assert target.value > current.value
+ ret.extend(self._parent_path(current.right, target))
+ return ret
+
+ def parent_path(self, node: Node) -> List[Optional[Node]]:
+ """Return a list of nodes representing the path from
+ the tree's root to the node argument. If the node does
+ not exist in the tree for some reason, the last element
+ on the path will be None but the path will indicate the
+ ancestor path of that node were it inserted.
+
+ >>> t = BinarySearchTree()
+ >>> t.insert(50)
+ >>> t.insert(75)
+ >>> t.insert(25)
+ >>> t.insert(12)
+ >>> t.insert(33)
+ >>> t.insert(4)
+ >>> t.insert(88)
+ >>> t
+ 50
+ ├──25
+ │ ├──12
+ │ │ └──4
+ │ └──33
+ └──75
+ └──88
+
+ >>> n = t[4]
+ >>> for x in t.parent_path(n):
+ ... print(x.value)
+ 50
+ 25
+ 12
+ 4
+
+ >>> del t[4]
+ >>> for x in t.parent_path(n):
+ ... if x is not None:
+ ... print(x.value)
+ ... else:
+ ... print(x)
+ 50
+ 25
+ 12
+ None
+
+ """
+ return self._parent_path(self.root, node)
+