I recently tried out SPOJ (Sphere Online Judge), and its pretty good for practicing algorithms. Here is a pretty simple SPOJ question.
The tree is undirected, meaning the connections can be given in any order.
The general idea is this. Start at any node, and traverse in depth first order, keeping track of the depth of the subtree under each node. We will also make sure we do not end up going in circles. Then, we just take the deepest child of the root, the second deepest child of the root, and add their depths and add 2 more edges : ones which connect the root to the two deepest children. There are a few edge cases. Try to think which, and how you'll handle them.
For trees, I really prefer to make a class and solve the question. I actually have a basic class ready for Binary Search Trees with all types of traversals (bread first, depth first and inOrder). I just had to copy that class in, and modify it for n-ary trees. Here is the class
#include<iostream>
#include<vector>
#include<queue>
struct Node {
int val;
int parent, left, right;
};
class BST {
private:
std::vector<Node> tree;
public:
Node* root = nullptr;
BST(std::vector<Node> _tree) :tree(_tree){
if (_tree.size() != 0) {
root = &tree[0];
}
else {
root = nullptr;
}
}
void InorderTraversal(Node* root) {
if (root == nullptr) {
return;
}
if (root->left != -1) {
InorderTraversal(&tree[root->left]);
}
std::cout << root->val << " ";
if (root->right != -1) {
InorderTraversal(&tree[root->right]);
}
}
void PreOrderTraversal(Node* root) {
if (root == nullptr) {
return;
}
if (root->left != -1) {
InorderTraversal(&tree[root->left]);
}
if (root->right != -1) {
InorderTraversal(&tree[root->right]);
}
std::cout << root->val << " ";
}
void BreadthFirstTraversal(Node* root) {
if (root == nullptr) {
return;
}
std::queue<Node*> Q;
Q.push(root);
while (!Q.empty()) {
std::cout << Q.front()->val << " ";
if (Q.front()->left != -1) {
Q.push(&tree[Q.front()->left]);
}
if (Q.front()->right != -1) {
Q.push(&tree[Q.front()->right]);
}
Q.pop();
}
}
};
std::vector<int> neighbors;this stores the index of all the nearest neighbors of that node, and since the tree is non-directional, if there exists an edge between 1 and 2, 1 appears in 2's neighbor list, and 2 appears in 1's neighbor list. So how do we avoid going in circles?
We add another boolean variable called "visited" to the node struct, which will be false by default.
bool visited = false;We will be using a depth first search in order to sift through the vertices, and find the depth. So let us add another data point to our struct which keeps track of the maximum depth of the subtree under a vertex.
int maxDepthOfSubtree = 0;While we do the DFS, we increase the depth as we move back up from the deepest point of the tree, meaning after our recursive call. So this variable is updated from the bottom up, not top to bottom, which is opposite to the direction of out DFS.
Our DFS first of all sets the visited status of the current node to true, then recursively scans each of it's non-visited neighbors. When the recursion returns, the value of maxDepthOfSubtree will be correct for all the neighbors, and so we can just add 1 to the maximum neighbor, and assign this value to maxDepthOfSubtree of the current node.
for (int child : root->children) {
if (!tree[child].visited) {
DFS(&tree[child]);
if (root->depthOfSubtree < tree[child].depthOfSubtree + 1) {
root->depthOfSubtree = tree[child].depthOfSubtree + 1;
}
}
}Now to return our answer, we simply compare the maxDepthOfSubtree of all the neighbors of our first node (which we will call the root), and add the two maximum subtree depths, and add 2 to them, edge cases being zero children and 1 child.
int MaxDist() {
DFS(root);
std::vector<int> depths;
for (int child : root->children) {
depths.push_back(tree[child].depthOfSubtree);
}
std::sort(depths.begin(), depths.end(), std::greater<int>());
if (depths.size() >= 2) {
return depths[0] + depths[1] + 2;
}
else if (depths.size() == 1) {
return depths[0] + 1;
}
else {
return 0;
}
}To be honest there isnt anything special about the root, unlike Binary Search Trees. Here, the root can be ANY node and it'll work. But since it IS definitely a tree, any node can be made the root, and it will remain a tree. That's why it works.
