# Find Duplicate Subtrees

• Can you briefly explain the lambda "x-> t++" in map.computeIfAbsent() please?

• @Nio `int uid = trees.computeIfAbsent(serial, x-> t++)` means something like:

if `serial` is not contained in `trees`, then `trees.put(serial, t++)` [make the value of this key `serial` equal to `t`, and then incremement `t`]

and after, `uid = trees.get(serial)`.

• Would you please explain how the second approach runs in O(n) and first in O(n square). Isn't it same as Approach 1 except the fact that we are using two hash tables and the key for second hash table is an integer instead of string.

• I think the first solution is also O(N), why O(N ^ 2)

• @jocelynayoga
In the first solution, every node creates a serialization of it's subtree, which is going to be quite large and take O(N) work per node (and there are N nodes.)

@bhawna1712
In the second solution, every node only creates a sort of pointer (val, left, right) which takes O(1) work and is significantly smaller.

• @awice but in both solutions, you need to call
String serial = node.val + "," + lookup(node.left) + "," + lookup(node.right);
which is the same. In the first solution, every node does not construct the string independently, it still visit each node once.

• @jocelynayoga String concatenation is linear time, so creating such a string with length L is O(L). The expected length of each serial is O(N).

For a concrete example, imagine the tree is just a line (every node has a left child except one leaf). Then the serials are like "A", "BA", "CBA", "DCBA", .... . Creating all of these is O(N^2) work.

• does this String serial = node.val + "," + lookup(node.left) + "," + lookup(node.right) take O(n)? It looks like both approach would require running this for every node. so both approach would take O(N2).

• Both these two solution use a similar recursive structure, the difference is just that the first solution returns string(which could be quite long) while the second returns a uid number. Hence both solution takes O(N) time, and the first takes O(N^2) space while the second takes O(N) space.

• Any way, the first solution is much faster than the second. the first takes 38ms beats 75% while the second takes 94ms beats 5%, both of them takes O(N) time. The reason slows the second might be that it uses two HashMap, any good analyse?

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.