First off, for pure data, I've been getting into using dataclasses for my values. This will take care of doing that __repr__ method and the constructor for you. Even better, if you can use a frozen dataclass, then it can also be used as a key in a dictionary, because it is safely hashable.
Using these tools, all you will need to do is count the unique instances of each node. You can use the Counter class or a simple defaultdict to do this. To find the nodes without recursion, you can use a queue.
import dataclasses
from collections import defaultdict
from typing import Optional
@dataclasses.dataclass(frozen=True)
class Node:
value: int
left: Optional["Node"] = None
right: Optional["Node"] = None
def find_node_counts(node):
node_counts = defaultdict(int)
search_queue = [node]
while search_queue:
# Allow safely adding None values to the queue
if curr_node := search_queue.pop():
search_queue.append(curr_node.left)
search_queue.append(curr_node.right)
# Because its frozen, and has a deterministic hash
# this will increment matching nodes correctly
node_counts[curr_node] += 1
return node_counts
Finding any duplicates is just checking if there any nodes with counts greater than 1.
n3_1 = Node(3)
n2_1 = Node(2, n3_1)
n3_2 = Node(3)
n2_2 = Node(2, n3_2)
n1 = Node(1, n2_1, n2_2)
node_counts = find_node_counts(n1)
for node, count in node_counts.items():
if count > 1:
print(f"Tree {node} appears {count} times")
Tree Node(value=2, left=Node(value=3, left=None, right=None), right=None) appears 2 times
Tree Node(value=3, left=None, right=None) appears 2 times
Note: If you want the tree to still be mutable, then you can do:
@dataclasses.dataclass(unsafe_hash=True)
class Node:
value: int
left: Optional["Node"] = None
right: Optional["Node"] = None
As a warning, if you do this then you need to make sure that you reconstruct any dictionaries relying the nodes any time you mutate part of the tree. This is because the underlying hash will change if you mutate the tree and you will get unexpected results.