self.depth = 5
...
def __calculateNodesNumber__(self):
return (4**(self.depth+1) - 1) // 3
def __isLeaf__(self, node):
return node.getChild(1) >= self.__calculateNodesNumber__()
This looks somewhat horrible, depth is is a constant, so why do you run a floating-point pow() computation every time someone asks for 'isLeaf' ?
One optimization can be to cache the answer after the first query.
if self.answer is None:
self.answer = (4**(self.depth+1) - 1) // 3
return self.answer
Secondly, 4 == 2**2, thus 4**(self.depth+1) == 2**(2*(self.depth+1)) == 1 << 2*(self.depth+1). Bit-shifting is a few order of magnitudes faster than any floating point computation.
Finally, as self.depth is constant, just compute and store the answer during construction:
self.depth = 5
self.nodes_number = ((1 << 2*(self.depth+1)) - 1) // 3
...
def __calculateNodesNumber__(self):
return self.nodes_number
further optimization may be possible depending on whether you actually need 'depth' or '__calculateNodesNumber__' at all.
By the way, your double leading and trailing underscore names are not advised by PEP8:
https://www.python.org/dev/peps/pep-0008/#descriptive-naming-styles , last item
__double_leading_and_trailing_underscore__ : "magic" objects or attributes that live in user-controlled namespaces. E.g. __init__ , __import__ or __file__ . Never invent such names; only use them as documented.