I recently had an interview problem where I was asked to find a compact representation of nodes in a tree.
As an example, consider the following tree:
A / | \ B C D / | \ | \ E F G H I /\ J K
The task was, given a list of node values, find a compact list of node values that completely describes the list given. A node value being in the list implictly means that all it's children are in the list as well and viceversa.
As a few examples, for the tree given:
compact([A]) = [A] compact([B, C, D, J]) = [A] compact([J, K]) = [E] compact([J, K, F, G]) = [B] compact([E, F, G, H]) = [B, H] compact([H, I, D]) = [D]
This was my recursive attempt in python (from memory so may be some mistakes/syntax errors), which would be called with the root of the tree first. I was told:
- I don't need to check for empty trees
- I can assume that each node has basic tree methods (so can check it's value, if it's a leaf node etc).
- The non-compact list of nodes values is passed in through node_list and I was told that there would be no duplicates in this list and that each value in it would correspond to a node in the tree
def compacted_tree(node, node_list): compact_list =  if node.value in node_list: #if this node is in the list then it is it's own consise representation return [node.value] allChildrenInCompactList = True for child in node.get_children(): compact_list.extend(compacted_tree(child, node_list)) if (allChildrenInCompactList): #only keep checking this if it's still true allChildrenInCompactList = child.value in compact_list if (allChildrenInCompactList and !node.isleaf()): #all my children are in the list so the compact list should just be me return [node.value] return compact_list
I said that this would run with complexity \$O(n^2)\$ (with n=number of nodes in the tree) as in the worst case, every node needs to be visited and, in the worst case, every node needs to check all it's children against the node_list which is an \$O(n)\$ operation too. I said the space complexity should be \$O(n)\$ as in the worst case you may have to add all your nodes to the
compact_list before it can simplify.
It was hard to get a good read of how I went from the interview but I'm yet to get a call back. The interviewer hinted that the task could have been done with better complexity but I fail to see how. He also said that my time complexity should have been not just in terms of the number of nodes in the tree but also the length of the
Is anyone able to tell me how I should've approached this problem/analysis better?