#!/usr/bin/env python3
+# © Copyright 2021-2022, Scott Gasch
+
+"""Binary search tree."""
+
from typing import Any, Generator, List, Optional
return self._find(value, node.right)
return None
- def _parent_path(
- self, current: Optional[Node], target: Node
- ) -> List[Optional[Node]]:
+ def _parent_path(self, current: Optional[Node], target: Node) -> List[Optional[Node]]:
if current is None:
return [None]
ret: List[Optional[Node]] = [current]
return x
path = self.parent_path(node)
- assert path[-1]
+ assert path[-1] is not None
assert path[-1] == node
path = path[:-1]
path.reverse()
for ancestor in path:
- assert ancestor
+ assert ancestor is not None
if node != ancestor.right:
return ancestor
node = ancestor
return self.depth()
def repr_traverse(
- self, padding: str, pointer: str, node: Optional[Node], has_right_sibling: bool
+ self,
+ padding: str,
+ pointer: str,
+ node: Optional[Node],
+ has_right_sibling: bool,
) -> str:
if node is not None:
viz = f'\n{padding}{pointer}{node.value}'
else:
pointer_left = "└──"
- viz += self.repr_traverse(
- padding, pointer_left, node.left, node.right is not None
- )
+ viz += self.repr_traverse(padding, pointer_left, node.left, node.right is not None)
viz += self.repr_traverse(padding, pointer_right, node.right, False)
return viz
return ""
else:
pointer_left = "├──"
- ret += self.repr_traverse(
- '', pointer_left, self.root.left, self.root.left is not None
- )
+ ret += self.repr_traverse('', pointer_left, self.root.left, self.root.left is not None)
ret += self.repr_traverse('', pointer_right, self.root.right, False)
return ret