425. Find All Duplicate Subtrees in a Binary Tree

Given a binary tree, find every subtree pattern (of 2 or more nodes) that occurs more than once anywhere in the tree. Print each distinct duplicated pattern exactly once, as its own level-order token line (using the platform's usual convention, trailing 'N's omitted), sorted alphabetically by that printed line; if there are no duplicates, print 'None'.

Input: A single line of space-separated level-order tokens describing the binary tree ('N' marks an absent child). Output: Print each distinct duplicated subtree pattern (size 2 or more) as its own level-order token line, sorted alphabetically, or print 'None' if there are no duplicates.

1 <= number of nodes <= 10^3

Sorting the final output lines alphabetically (as this problem explicitly requires) needs to happen on the PRINTED level-order strings, not on the internal post-order canonical serialization used purely for detecting duplicates.

Find every subtree pattern (of 2 or more nodes) that occurs more than once anywhere in a binary tree, and print each distinct duplicated pattern once. Brute force: Compare every pair of subtrees directly for structural and value equality - this costs O(n²) or worse, since each individual comparison can itself take time proportional to the subtree's size. Optimised: The same canonical-serialization-plus-hashmap technique used for the yes/no duplicate-subtree CHECK extends directly here - the only difference is that instead of just checking IF any canonical form repeats, you collect and report every one that does, filtered to size 2+ and sorted for deterministic output.

During a single post-order traversal, instead of building a full string per subtree, assign each node an integer ID derived from the triple (leftChildID, value, rightChildID) via a hashmap from triple to a running counter, reusing an existing ID if that exact triple has been seen before, or minting a new one otherwise. Two subtrees have the same integer ID if and only if they are identical, but computing it takes only O(1) work per node (not O(size of subtree)), because it only ever looks at the already-computed IDs of the two children rather than re-walking them. A second hashmap counts how often each ID occurs, and the duplicated patterns are those crossing count 2, reconstructed for output. This drops the true total cost to linear in the number of nodes. Time: O(n) average Space: O(n)

For every node in the tree, serialize the subtree rooted at it (e.g. preorder with 'N' for missing children) into a string. Then compare every subtree's serialization against every other subtree's serialization pairwise to count how many times each pattern occurs, collecting patterns that occur more than once. This is correct since identical serializations correspond exactly to structurally-and-value identical subtrees, but comparing all pairs of (potentially long) strings is very costly. Time: O(n^2) serializations, O(n) each -> O(n^3) worst case Space: O(n^2)

Do a single post-order traversal, serializing each subtree into a string exactly once, and store these strings as keys in a hashmap counting occurrences. Any serialization with count exactly 2 (the moment it becomes a duplicate) identifies a duplicated subtree pattern. This replaces the pairwise O(n^2) string comparisons with O(1) amortized hashmap operations per subtree, though building each subtree's string is still proportional to its size, so the total string-construction cost across all nodes is still quadratic in the worst case (e.g. a skewed tree). Time: O(n^2) worst case (string building dominates) Space: O(n^2) worst case (storing all serialized strings)

1. Serialize every subtree canonically (its shape plus values, using a sentinel like '#' for missing children) in a single post-order pass, counting occurrences of each canonical form with a hashmap. 2. Ignore any canonical form belonging to a subtree of size 1 (a lone repeated leaf value doesn't count). 3. For every canonical form occurring 2 or more times, print that subtree's own level-order serialization once - then sort all the printed lines alphabetically for a deterministic order.

Time: O(n) on average with hashing (each subtree's serialization built from already-computed children's serializations, reused directly). Space: O(n²) in the worst case for storing all serialized strings (bounded by each subtree's own size), though this can be reduced with integer IDs assigned per unique serialization instead of storing full strings repeatedly.

Test with a repeated leaf value only (must not count, expect 'None'), multiple distinct duplicated patterns requiring alphabetical ordering, and a tree at the maximum size of 10^3 nodes for performance.

Be ready to explain the small but important extension from the yes/no check to the full-listing version - collecting one REPRESENTATIVE serialization per duplicated canonical form, rather than just a boolean flag.