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.
| #include <iostream> | |
| #include <vector> | |
| using namespace std; | |
| int depth(int nodeId, const vector<int> & parent, vector<int> & d) | |
| { | |
| if( parent[nodeId] == -1 ) | |
| { | |
| d[nodeId] = 0; | |
| } | |
| else | |
| { | |
| //if depth of parent is already calcualted | |
| if( d[ parent[nodeId] ] != -1 ) | |
| { | |
| d[nodeId] = d[parent[nodeId]] + 1; | |
| } | |
| else | |
| { | |
| //recursively call depth function for parent | |
| d[nodeId] = depth( parent[nodeId], parent, d ) + 1; | |
| } | |
| } | |
| return d[nodeId]; | |
| } | |
| int findDepth( const vector<int> & parent ) | |
| { | |
| vector<int> d( parent.size(), -1 ); | |
| //Calculate depth for each node | |
| int i; | |
| for( i = 0; i < parent.size(); i++ ) | |
| { | |
| d[i] = depth(i, parent, d); | |
| } | |
| //find maximum of depths of all nodes | |
| int maxDepth = 0; | |
| for( i = 0; i < parent.size(); i++ ) | |
| { | |
| maxDepth = max(maxDepth, d[i]); | |
| } | |
| return maxDepth; | |
| } | |
| int main() | |
| { | |
| int n;//number of nodes | |
| cin >> n; | |
| //to store parent node ids of each node; -1 indicates no parent | |
| vector<int> parent(n,-1); | |
| int i; | |
| //Read parent ids for each node | |
| for( i = 0; i < n-1; i++ ) | |
| { | |
| int nodeId, parentId; | |
| cin >> nodeId >> parentId; | |
| parent[nodeId] = parentId; | |
| } | |
| cout << findDepth( parent ) << endl; | |
| return 0; | |
| } |
by