Your code is compact, and yet still highly readable. Nice work! Here are some suggestions:
Avoid Global Data
The tree
and n
variables are global data meaning that any function anywhere in your application can change them. This makes it very difficult to follow the flow of control and figure out where data is modified. It's not a big deal for this little program, but there's no reason you can't put them into main()
.
Also, while we're talking about your variables, n
is not a terribly descriptive name. I would call it something like numNodes
or something along those lines.
Don't Traverse the Tree So Many Times
In your Height()
function you traverse the tree
n^2 times! At the very least, once you've found the parent you shouldn't traverse the rest of the array. But an even better way is to only traverse the entire tree once.
That's what I did in the example below. Note that I couldn't try it out on the website you mentioned because it requires one to sign up for an online course, and as you mentioned, the site was in Russian which I don't understand.
The first thing I did differently was to make a data structure to hold my node data. While the input only contains integers, that doesn't mean that you have to only put integers into your array. I created a type called Node
that holds the parent index, a pointer to the actual parent node, and an array of pointers to child nodes. It looks like this:
typedef struct Node {
int parentIndex = { kParentUnset };
Node* parent = { nullptr };
std::vector<Node*> children;
} Node;
Which reminds me of my next point - it's a good idea to avoid magic numbers like -1
bare in your code. I made some enum
s to describe different values for parentIndex
:
enum {
kNoParent = -1,
kParentUnset = -2
};
This makes the code a little easier to read and understand.
You'll notice that I also didn't actually use C arrays, but instead went with std::vector<>
. I did this because it allows me to add and remove items without knowing the size ahead of time, and to avoid putting a large block of data on the stack. It's also more standard C++.
So what this code does is read in the number of nodes and the parents of each node. As it reads in a parent, it not only sets the next node's parent index, it also actually sets the pointer to the parent and adds the current node to the parent's list of children. By the time the for
loop in main()
is complete, we have the entire tree built in memory. The fact is, we don't even need the parent indexes anymore. We could just discard that field, but I've left it to be more clear.
Next, we traverse the tree and calculate the maximum height. This is done using a depth first search. I implemented the search without recursion again to save space on the application stack and avoid a potential stack overflow. We start with the root node and push it onto our local stack variable. Then we enter a loop where we increment the current height, and see if it's greater than the max. If so, we set the max to the current height. Next, we pop the top off the stack. If it has no children, we've hit a leaf node. We decrement the current height and continue on. If it does have children, we push each one onto the stack and loop again.
Here's the code:
int findTreeHeight(Node* rootNode)
{
int maxHeight = 0;
std::stack<Node*> nodeStack;
nodeStack.push(rootNode);
int currentHeight = 0;
while (nodeStack.size() > 0)
{
currentHeight++;
if (currentHeight > maxHeight)
{
maxHeight = currentHeight;
}
Node* top = nodeStack.top();
nodeStack.pop();
if (top->children.size() == 0)
{
currentHeight--;
}
for (auto iter = top->children.begin(); iter < top->children.end(); iter++)
{
nodeStack.push(*iter);
}
}
return maxHeight;
}
int main ()
{
int numNodes = 0;
std::cin >> numNodes;
std::vector<Node> tree(numNodes);
int rootNodeIndex = -1;
for (int i = 0; i < numNodes; ++i)
{
int parentIndex;
std::cin >> parentIndex;
tree [ i ].parentIndex = parentIndex;
if (parentIndex == kNoParent)
{
rootNodeIndex = i;
}
else
{
tree [ i ].parent = &tree [ parentIndex ];
tree [ parentIndex ].children.push_back(&tree [ i ]);
}
}
std::cout << findTreeHeight(&tree [ rootNodeIndex ]) << "\n";
return 0;
}