key_of(node) is defined by one sentence: it returns a string that describes the subtree at node. The code only has to keep that sentence true for one call, and the sentence then holds for every call.

A missing child returns #. For a real node, left_key and right_key are the true descriptions of its two subtrees, by the same sentence. The key of the node is its value, then left_key, then right_key, with commas between them. So the key lists the nodes in preorder, and it lists a # for every missing child.

Two different subtrees cannot get the same key. Read a key from the left. The first part is the value of the root. The next parts describe the left subtree, and they end exactly where that subtree ends, because every real node is followed by two keys and every # ends a branch. What remains describes the right subtree. So a key can be read in only one way, and it describes one tree.

Take root = [1, 2, 3, 4, null, 2, 4, null, null, 4]. The three leaves 4 each get the key 4,#,#. The two nodes 2 each have one left child 4, so both get the key 2,4,#,#,#. The count of 4,#,# reaches 2 at the second leaf, and the count of 2,4,#,#,# reaches 2 at the second node 2. So repeated becomes [4, 2], and sorted(repeated) is [2, 4].

The walk makes 13 calls: 6 calls on real nodes and 7 calls on missing children.

Suppose the key skips a child that is missing. A node 1 with only a left child 2 gets the key 1,2. A node 1 with only a right child 2 also gets the key 1,2. These are different shapes with the same key.

On root = [0, 1, 1, 2, null, null, 2], the left 1 and the right 1 get the same key, so 1 is reported as repeated. The correct answer is [2], because only the leaf 2 appears twice. The code that skips the missing child returns [1, 2].

The # for a missing child fixes this. It keeps the position of every part: the left 1 gets 1,2,#,#,# and the right 1 gets 1,#,2,#,#.

The separators matter too. Without commas, a node 1 with a left child 11 gets 111###, and a node 11 with a left child 1 gets the same 111###. On root = [0, 1, 11, 11, null, 1] the code without commas reports 11, and the correct answer is [].

A test for your own key: can you write down two different trees that give the same string? If you can, add a marker or a separator until you cannot.

In Find Duplicate Subtrees (LC 652) the strings are keys. They are counted and never printed. In the other problems on this card, the same string is the answer, or it is used for a lookup.

In Serialize and Deserialize Binary Tree (LC 297), the key of the root is the answer. For [1, 2, 3, null, null, 4, 5] it is 1,2,#,#,3,4,#,#,5,#,#. To read it back, take one token at a time. A # is a missing node. Any other token is a node, and the next calls read its left subtree and then its right subtree. The tree built from this string gives the same string again.

In Construct String from Binary Tree (LC 606), the marker is a pair of parentheses, and the key is value(left)(right). A missing right child can be dropped. A missing left child must stay as () when a right child exists. For [1, 2, 3, null, 4] the answer is 1(2()(4))(3). The () that stays is the same marker as #: without it, a left child and a right child would look the same.

In Delete Duplicate Folders in System (LC 1948), the key of a folder is built from its subfolders only. It lists each subfolder's name followed by that subfolder's key, with the subfolders sorted by name. The name of the folder itself is not in its key, because two folders with different names can be identical. A non-empty key that appears twice or more marks all of those folders for deletion.

In Subtree of Another Tree (LC 572), build the key of subRoot, and check whether it is the key of any subtree of root.

A key is as long as its subtree. Joining it and reading it for the dictionary costs time in proportion to its length. The lengths of all keys add up to the sum of the subtree sizes.

On a complete tree of 1023 nodes with every value 0, the keys add up to 37,891 characters. On a chain of 1000 nodes with every value 0, they add up to 2,003,000 characters. In the worst case the sum is N * (N + 1) / 2 subtree nodes, so the time and the space are O(N^2).

When N is large, give each different key a small number instead of a string. The key of a node is then the triple (node.val, left_id, right_id), and a dictionary turns each new triple into the next number. Every key has a fixed size, so the time and the space are O(N). Two subtrees get the same number exactly when they have the same shape and the same values.

A chain of 5000 nodes is 5000 calls deep, which is past Python's default limit of about 1000 nested calls. Raise the limit with sys.setrecursionlimit, or walk the tree with an explicit stack.