Given a tree, find the common subtrees and replace the common subtrees and compact the tree. e.g.

      1
     /  \
     2   3
   / |   /\
  4  5  4  5

should be converted to

      1
     /  \
     2   3
   / |   /\
  4  5   | |

  ^  ^   | |

  |__|___| |

     |_____|

this was asked in my interview. The approach i shared was not optimal O(n^2), i would be grateful if someone could help in solutioning or redirect me to a similar problem. I couldn't find any. Thenks!

edit- more complex eg:

       1
     /  \
     2   3
   / |   /\
  4  5  2  7
       /\
      4  5

whole subtree rooted at 2 should be replaced.

      1
     /  \
     2 <--3
   / |     \
  4  5      7
    

CodePudding user response：

You can do this in a single DFS traversal using a hash map from (value, left_pointer, right_pointer) -> node to collapse repeated occurrences of the subtree.

As you leave each node in your DFS, you just look it up in the map. If a matching node already exists, then replace it with the pre-existing one. Otherwise, add it to the map.

This takes O(n) time, because you are comparing the actual pointers to the left right subtrees, instead of traversing the trees to compare them. The pointer comparison gives the same result, because the left and right subtrees have already been canonicalized.

CodePudding user response：

Firstly, we need to store the node values that appear in a hash table. If the tree already exists, we can iterate the tree and if a node value is already in the set of nodes and delete the branches of that node. Otherwise, store the values in a hash map and each time, when a new node is made, check if the value appears in the map.