Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
First solution in Uncategorized category for Tree Walker by Fornit
from collections import deque
from dataclasses import field, dataclass
from typing import List, Deque
@dataclass
class Node:
value: object = None
leafs: List['Node'] = field(default_factory=list, repr=False)
def __post_init__(self):
if isinstance(self.value, list):
for x in self.value:
self.add_leaf(x)
self.value = list()
elif isinstance(self.value, dict):
for k, v in self.value.items():
self.add_leaf(k).add_leaf(v)
self.value = dict()
def add_leaf(self, value):
leaf = Node(value=value)
self.leafs.append(leaf)
return leaf
@dataclass
class Tree:
root: Node
def count(self, target) -> int:
res = 0
queue: Deque[Node] = deque([self.root])
target = Node(target)
while len(queue) > 0:
next_node = queue.popleft()
if next_node == target:
res += 1
elif len(next_node.leafs) > 0:
queue.extend(next_node.leafs)
return res
def tree_walker(tree, target):
t = Tree(Node(value=tree))
return t.count(target)
if __name__ == '__main__':
print("Example:")
print(tree_walker([1, "2", 3, [[3], 1, {1: "one"}]], 1))
# These "asserts" are used for self-checking and not for an auto-testing
assert tree_walker([1, "2", 3, [[3], 1, {1: "one"}]], 1) == 2, "1st"
assert tree_walker({"one": 1, "two": [{1: "one", 2: "two"}, 1, "1", "one"]}, 1) == 2, "2nd"
assert tree_walker({"one": [1, 2], "two": [{1: "one", 2: "two"}, [1, 2], "1", "one"]}, [1, 2]) == 2, "3rd"
assert tree_walker(5, 5) == 1, "4th"
assert tree_walker([5, 6, 2, "1"], 1) == 0, "5th"
assert tree_walker([[dict()], [[[3], [3, 5]]], [], []], 3) == 2, "6th"
assert tree_walker([{1: "one"}, {2: "two"}, "two", ["two", {"two": "one"}]], "two") == 3, "7th"
print("Coding complete? Click 'Check' to earn cool rewards!")
July 23, 2020
