# Number of Nodes in Isolation Forest

I am currently reading this paper on Isolation Forest.

At page 3, there is a definition of Isolation Tree and there are a couple of sentences that I don't understand:

Given a sample of data X = {x1, ..., xn} of n instances from a d-variate distribution, to build an isolation tree (iTree), we recursively divide X by randomly selecting an attribute q and a split value p, until either: (i) the tree reaches a height limit, (ii) |X| = 1 or (iii) all data in X have the same values.

Here, I would like to understand what do the points (ii) & (iii) mean. In the point (iii), when the author says 'all data in X have same values', does it mean the same anomaly score?

And there is also a block of text which I am failing to understand completely. Can someone help me understand this text too..

Assuming all instances are distinct, each instance is isolated to an external node when an iTree is fully grown, in which case the number of external nodes is n and the number of internal nodes is n − 1; the total number of nodes of an iTrees is 2n − 1

Thanks

Isolating an instance means splitting the data until that instance ends up in a leaf by itself. If you have $$n$$ instances, you will need $$n$$ external ("end") nodes. One for each instance. The internal nodes are all the nodes before the end nodes, including the root that contains all the instances. One can show that their number is $$n-1$$. For example, if you have $$n=4$$ you can split it in (4)-(2,2)-((1,1)(1,1)). So you have $$1+1+1+1=4=n$$ end nodes, and $$1+2=3=n-1$$ inner nodes.
The total is therefore the number of end nodes plus the number of inner nodes $$n +(n-1) = 2n-1$$.