What would be the time complexity for the encode function? I think it should be O(v + e) + O(v * k * clogc), where v = num nodes, e = num edges, c = number of children & k = length of subtree encoding. For every node in the tree, we are sorting labels array which consists of node.children.size() (c) strings each of length let's say k (multiple of 2) so it would take (k * clogc) in sorting encodings of subtrees and for every v vertex in the tree time would be O(v * k*clogc). Is this analysis correct? If yes how to express k and c in terms of v and e.
In last video, each treeNode is defined as a class with id, parent and children. Apparently each node is only linked only to its neighbors now using adjacency list and the class is reduced to an integer id. It would be helpful to point out the gap since the representation changed a bit and it affects the implementation.
Feels really nice when you are able to code this all on your own. Thanks a lot man. Your lectures are a blessing.
I am definitely going to have to watch this more than 8-12 times.
Thanks for the effort you put in these :)
What would be the time complexity for the encode function?
I think it should be O(v + e) + O(v * k * clogc), where v = num nodes, e = num edges, c = number of children & k = length of subtree encoding.
For every node in the tree, we are sorting labels array which consists of node.children.size() (c) strings each of length let's say k (multiple of 2) so it would take (k * clogc) in sorting encodings of subtrees and for every v vertex in the tree time would be O(v * k*clogc).
Is this analysis correct? If yes how to express k and c in terms of v and e.
This is awesome. I learned a lot from you.
awesome, could anyone tell how to implement the lexicographic sorting in c++
It would have been good if you could explain what is the structure of the trees, and how your representing them.
How is the tree represented as List ?
It is a adjacency list. You could refer to the first video in the playlist...
In last video, each treeNode is defined as a class with id, parent and children. Apparently each node is only linked only to its neighbors now using adjacency list and the class is reduced to an integer id. It would be helpful to point out the gap since the representation changed a bit and it affects the implementation.
What if the first tree has two children?
you mean two center nodes