Ternary tree paths

Question

I'm solving the following question:

Given a ternary tree (each node of the tree has at most three children), find all root-to-leaf paths.

Example:

My code is as follows:

from __future__ import annotations

import itertools
from collections import deque, Iterable


class TernaryNode:
    def __init__(self, val: int) -> None:
        self.children: list[TernaryNode] = []
        self.val = val

    def __repr__(self) -> str:
        return str(self.val)


def ternary_tree_paths(root: TernaryNode) -> Iterable[Iterable[int]]:
    def _visit(node: TernaryNode) -> Iterable[deque[int]]:
        if not node:
            return []
        if not node.children:
            queue = deque()
            queue.append(node.val)
            return [queue]
        # **
        paths = itertools.chain.from_iterable(map(lambda ch: _visit(ch), node.children))
        for p in paths:
            p.appendleft(node.val)

        return paths

    return _visit(root)

As shown, the code above returns an empty list, where as the desired behavior is [deque([1, 2, 3]), deque([1, 4]), deque([1, 6])]. Note the line with **; if I rewrite that line as paths = [p for ch in node.children for p in _visit(ch)], it works as expected. I'm guessing the problem is because function from_iterable is evaluated lazily, but shouldn't it be forced to evaluate when I'm iterating over the items?

There is no actual tree defined in your code. Does the code above exhibit your error? No it doesn't. So it's not a [mre]. — Julien, May 17 '21 at 06:51
All I said is that it would be nice to provide an example that can be copied and pasted, rather than expecting people to to code that by themselves from a picture. You are of course not obliged to as nice as people who still try to help you. Have a good day :) — Julien, May 17 '21 at 06:57
Does this answer your question? [Python: calling 'list' on a map object twice](https://stackoverflow.com/questions/36486950/python-calling-list-on-a-map-object-twice) — MisterMiyagi, May 17 '21 at 07:05
Does this answer your question? [Resetting an iterator, which is a map object?](https://stackoverflow.com/questions/60304880/resetting-an-iterator-which-is-a-map-object) — MisterMiyagi, May 17 '21 at 07:07
@MisterMiyagi I've converted the `**` to a aid with copy-pasting. — Abhijit Sarkar, May 17 '21 at 07:07
Does this answer your question? [Why can't I iterate twice over the same data?](https://stackoverflow.com/questions/25336726/why-cant-i-iterate-twice-over-the-same-data) — MisterMiyagi, May 17 '21 at 07:08
@MisterMiyagi If you can make up your mind which of the answers is actually relevant to my question, perhaps I can read it and see if it helps. Pasting several links that you think is pertinent is not exactly helpful. — Abhijit Sarkar, May 17 '21 at 07:10
@AbhijitSarkar All of them. If I had to pick, the third fits the issue best, whereas the first two fit the use-case best. Depends on how much abstraction you want in an answer. — MisterMiyagi, May 17 '21 at 07:13

score 1 · Accepted Answer · answered May 17 '21 at 06:28

You're exhausting the chain iterable when trying to do the appendleft to each of the items. After that paths is empty.

You need to make sure the iterable is evaluated only once:

def ternary_tree_paths(root: TernaryNode) -> Iterable[Iterable[int]]:
    def _visit(node: TernaryNode) -> Iterable[deque[int]]:
        if not node:
            return []
        if not node.children:
            queue = deque()
            queue.append(node.val)
            return [queue]
        paths = itertools.chain.from_iterable(map(_visit, node.children))
        retval = [] # to keep track of results
        for p in paths: # iterate
            p.appendleft(node.val)
            retval.append(p) # add to result

        return retval # return result

    return _visit(root)

This yields:

[deque([1, 2, 3]), deque([1, 4]), deque([1, 6])]

For the example in the question.

Thanks. Seems like using a list solves this issue without needing an additional list `retval`. — Abhijit Sarkar, May 17 '21 at 07:16

Ternary tree paths

1 Answers1