Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
walk tree exactly once without recursion solution in Clear category for On the same path by juestr
from typing import FrozenSet, Iterable, List, Set, Tuple, Union
Node = Union[int, str]
Tree = Tuple[Node, List['Tree']]
Path = FrozenSet[Node]
def on_same_path(tree: Tree, pairs: List[Tuple[Node, Node]]) -> Iterable[bool]:
def paths(tree) -> Iterable[Path]:
stack = [(tree, frozenset())]
while stack:
(node, children), path = stack.pop()
newpath = path.union((node,))
for child in children:
stack.append((child, newpath))
if not children:
yield newpath
occurences = ([n1 in path and n2 in path for n1, n2 in pairs] for path in paths(tree))
return [any(pair_results) for pair_results in zip(*occurences)]
Dec. 27, 2019
Comments: