While trying to solve a set of question for an interview in Python, I came across this one which seemed easy at first, but I decided to share it here because I'm stuck on it for a while and I can't find a similar task online, here it goes:

A tree is an abstract data structure consisting of nodes. Each node has only one parent and zero or more child nodes. Each tree has one special node, called a root, which has no parent node. A node is called an internal node if it has one or more children.

A tree can be represented by a list P where P[i] is the parent of node i. For the root node r, P[r] equals -1.

Write a function that, efficiently with respect to time used, counts the number of internal nodes in a given tree.

For example, the tree represented by the list [1, 3, 1, -1, 3] has 5 nodes, 0 to 4, of which 2 nodes are internal nodes (only nodes 1 and 3 have children).

CodePudding user response：

The idea is that you count the number of distinct values that you encounter in the P list, except for the value -1, which should not be counted.

When you do that you have counted all nodes that are the parent of at least one node, and have the answer.

Depending on the programming language you can use a hash set for counting (a set in Python), or just an array/list (since your nodes are identified by indices) having a 1 for each found value, and 0 otherwise. Then sum up the 1 values.

So, for the example input [1, -1, 1, -1, 3], there are 2 distinct values (ignoring -1): 1 and 3.

In python:

internal_node_count = max(0, len(set(P)) - 1)

The max function makes sure that the result cannot be negative -- this is only needed for when the input list is empty and thus has no -1 in it.