Find Duplicate Subtrees Python Solution

Tested Python solution for LeetCode 652 with 12 pytest cases. Generate a practice environment with lcpy.

LeetCode 652, Medium. Topics: Hash Table, Tree, Depth-First Search, Binary Tree. View on LeetCode.

Generate this problem as a practice environment: tested reference solution, 12 parametrized pytest cases, and a playground notebook:

lcpy gen -n 652   # by problem number
lcpy gen -s find_duplicate_subtrees   # by problem name

​

Problem

Given the root of a binary tree, return all duplicate subtrees.

For each kind of duplicate subtrees, you only need to return the root node of any one of them.

Two trees are duplicate if they have the same structure with the same node values.

​

Examples

Input: root = [1,2,3,4,null,2,4,null,null,4]
Output: [[2,4],[4]]

Input: root = [2,1,1]
Output: [[1]]

Input: root = [2,2,2,3,null,3,null]
Output: [[2,3],[3]]

​

Constraints

• The number of the nodes in the tree will be in the range [1, 5000]
• -200 <= Node.val <= 200

​

Solution

Reference implementation from solution.py on GitHub, full suite in test_solution.py:

from collections import Counter

from leetcode_py import TreeNode


class Solution:
    # Time: O(n^2) worst case for string serializations
    # Space: O(n^2)
    def find_duplicate_subtrees(self, root: TreeNode[int] | None) -> list[TreeNode[int] | None]:
        counts: Counter[str] = Counter()
        result: list[TreeNode[int] | None] = []

        def serialize(node: TreeNode[int] | None) -> str:
            if node is None:
                return "#"
            key = f"{node.val},{serialize(node.left)},{serialize(node.right)}"
            counts[key] += 1
            if counts[key] == 2:
                result.append(node)
            return key

        serialize(root)
        return result

​

Complexity

Time	Space
O(n^2) worst case for string serializations	O(n^2)

​

Tags

NeetCode All.