Find Duplicate Subtrees (Postorder & Map)

To solve the Find Duplicate Subtrees problem, I would utilize a postorder traversal combined with a HashMap to track serialized subtree patterns. First, I need to ensure we understand that a duplicate means both the structure and the node values match exactly. My approach starts by defining a recursive helper function. In this function, I will traverse the left child, then the right child, and finally process the current node. This postorder sequence is crucial because it ensures we have fully serialized the children before combining them with the parent. For serialization, I will construct a string representation for each subtree. A robust format would be 'NodeValue,LeftSubtreeString,RightSubtreeString', using a special character like '#' to represent null nodes. This guarantees uniqueness; for instance, a tree with value 1 and a single left child 2 differs from a tree with value 1 and a single right child 2. As I build these strings, I will insert them into a HashMap where the key is the string and the value is an integer count. Whenever the count for a specific string transitions from one to two, I know I have found a duplicate subtree. At that moment, I can add the current root node to my result list. If Microsoft requires only one representative, I stop after the first duplicate found. This solution operates in O(N) time since we visit every node once, and O(N) space for the map and recursion stack, assuming average string lengths are proportional to subtree size.