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

• G. Sliepen: There are some obvious errors in your code. In dup_trees(), inside the if(root.right), you store root.left.value in the map. You also don't correctly handle the case where both left and right children are present, and you only store the immediate values, not the whole subtrees. You should use some larger test cases.
• beatmaister: @G.Sliepen I see now, I am only storing the children of each root rather than whole trees. I'll try again

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.

• beatmaister: Slightly embarrassingly, this is my first time hearing of dataclasses. I see now that searching and logging counts of each tree's occurrence is much cleaner. Thanks!