Find ALL duplicate subtrees. using recursion

Question

This is just a practice exercise, I'm trying to understand dynamic programming as deeply as I can. I solved this using recursion, though I am not sure if it will always work. If anyone could tell me a case in which my solution does not work. And I would also appreciate knowing the time/space complexities of this solution. knowing a binary tree is usually \$\mathcal{O}(n^2)\$, I believe my solution is \$\mathcal{O}(n)\$.

AKA. Please tell me how efficient my solution is, if at all. Thanks.

class Node: def __init__(self, value, left=None, right=None): self.value = value self.left = left self.right = right def __repr__(self): if self.left and self.right: return f"({self.value}, {self.left}, {self.right})" if self.left: return f"({self.value}, {self.left})" if self.right: return f"({self.value}, None, {self.right})" return f"({self.value})" map={} def dup_trees(root): if(root.left): print("left found") try: if map[root.value]: print("duplicate Left") except KeyError: map[root.value]= str(root.value)+','+str(root.left.value) if(root.right): print("right found") try: if map[root.value]: print("duplicate Right") except KeyError: map[root.value]= str(root.value)+','+str(root.left.value) elif(not root.left and not root.right): print("no left or right") try: if map[root.value]: print("duplicate Leaf") except KeyError: map[root.value]= str(root.value)+',X' if root.left: dup_trees(root.left) if root.right: dup_trees(root.right) 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) dup_trees(n1) print(map) # Looks like # 1 # / \ # 2 2 # / / # 3 3 # There are two duplicate trees # # 2 # / # 3 # and just the leaf # 3 

Answer 1

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.