'binary tree compaction of same subtree

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
algorithmdata-structurestreebinary-tree


Solution 1:[1]

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.

Solution 2:[2]

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.

Sources

This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.

Source: Stack Overflow

Solution Source
Solution 1 Matt Timmermans
Solution 2 Fuex Follets

Related Questions