Given an a rooted n-ary tree represented as a parent id array, Write a program to find the depth of it.
The depth of a tree is defined as the maximum length of the path from root to any leaf node.
For example the following tree has a depth of 2 (for the path 0-2-4)
It is represented in parent id array as follows
index: 0 1 2 3 4
parent: -1 0 0 0 2
This can be solved by first finding the depth of each node and returning the maximum among them. We can find the depth of each node by traversing the parent ids until we reach the root node. But this method takes O(n2) time if we naively calculate the depth of each node.
For example we calculate the depth of node 0 every time when we calculate the depths of it’s descendants (1,2,3,4).
We need to use a simple memorization (Dynamic Programming) to store the depths of nodes already calculated.
For example if we already have the depth of 2, then the depth(4) is depth(2)+1.
This method runs in O(n) time because each node is visited exactly once. space complexity is O(n).
The following is a C++ implementation of the above DP algorithm.