416. Check for Duplicate Subtrees of Size 2 or More

Given a binary tree, print 'Yes' if it contains at least two subtrees (each with 2 or more nodes) that are structurally identical - same shape and same values at every corresponding position - otherwise print 'No'. A single repeated leaf value does not count, since a lone leaf is a subtree of size 1. The tree is given as space-separated level-order tokens, where 'N' means no node there: the first token is the root, then for each node dequeued in level order you read its left-child token then its right-child token (if input runs out early, remaining children are treated as N).

Input: A single line of space-separated level-order tokens describing the binary tree ('N' marks an absent child). Output: Print 'Yes' if at least two structurally identical subtrees of size 2 or more exist, otherwise print 'No'.

1 <= number of nodes <= 10^5

The problem explicitly excludes single-leaf duplicates (subtrees must have 2+ nodes) - filtering out size-1 serializations before checking for duplicates is a small but necessary detail to match the problem's exact requirement.

Check whether a binary tree contains two separate subtrees (each with at least 2 nodes) that are structurally and value-wise identical. Brute force: Compare every pair of subtrees directly, checking node-by-node if their structures and values match - this costs O(n²) or worse in the worst case, since comparing two subtrees itself takes time proportional to their size. Optimised: Serializing each subtree into a single canonical STRING (via post-order, so a node's full serialization only depends on already-computed children's serializations) lets you use a hashmap to detect duplicates directly by string equality, checked once per node - turning an expensive pairwise comparison problem into a single linear pass with hash lookups.

Traverse the tree bottom-up (e.g. postorder), and at each node build a string that serializes the subtree rooted there, such as 'value,leftSerialization,rightSerialization', using a fixed marker like 'N' for missing children so shape differences are captured too. Store every such serialization (for subtrees of size 2 or more) and check whether any string appears more than once. This avoids the pairwise O(n^2) comparisons of brute force, since equal serializations exactly mean structurally identical subtrees, but building and comparing full strings at every node still costs time proportional to subtree size, and larger subtrees produce longer strings that are expensive to hash or compare. Time: O(n^2) worst case due to string construction Space: O(n^2)

Collect every node of the tree, and for every pair of distinct nodes, recursively compare the subtrees rooted at each of them to check whether they have identical shape and identical values at every corresponding position, skipping any subtree of size 1 since a single repeated leaf value doesn't count. If any pair of size-2-or-larger subtrees matches, print 'Yes'. This directly implements the definition of a duplicate subtree, but comparing every pair of nodes, each comparison itself potentially touching many nodes, is extremely wasteful. Time: O(n^2 * h) Space: O(h)

Traverse the tree bottom-up, and instead of building a full string for each subtree, assign every distinct node signature (value, left child's ID, right child's ID) a small integer ID via a hashmap, so equal subtrees always map to the same ID and the ID for a node can be computed in O(1) once its children's IDs are known. Track how many times each ID (for subtrees of size 2 or more) has been assigned, and if any ID reaches a count of 2 or more, a duplicate subtree exists. Because each node now does only constant work using its children's already-computed IDs, this avoids ever building or comparing long strings, bringing the whole check down to a single linear pass. Time: O(n) Space: O(n)

1. Do a post-order traversal, and for every node, build a CANONICAL string describing its entire subtree's shape and values (using a sentinel like '#' for missing children so different shapes can't accidentally produce the same string). 2. Use a hashmap counting how many times each canonical string has occurred. 3. The moment any canonical string (for a subtree with 2+ nodes) has occurred more than once, answer Yes.

Time: O(n) on average with hashing (assuming reasonably fast string hashing), though technically O(n²) in a rare worst case if serialized strings are very long and compared character-by-character on hash collisions. Space: O(n²) in the worst case for storing all serialized strings (since a serialization can be as long as its subtree's own size, and there are n subtrees total) - a more memory-efficient approach assigns each unique serialization a small integer ID instead of storing the full string repeatedly.

Test with a repeated leaf value only (must not count, expect 'No'), a tree containing two identical two-node subtrees, and a tree with 10^5 nodes for performance.

Be ready to explain why using a sentinel value (like '#') for missing children in the serialization is essential - without it, structurally DIFFERENT shapes (like a node with only a left child versus only a right child) could accidentally produce the same serialized string.