Why does this method return me 2?

Question

I have a code to analyze and I’m not sure understand why this method of my Binary Tree returns me 2.

Code:

class No:
def __init__(self, dado):
    self.esq = None
    self.dir = None
    self.dado = dado 

class Arvore:
def __init__(self):
    self.raiz = None
def pegarRaiz(self):
    return self.raiz

def inserir(self, val):
    if self.raiz == None:
        self.raiz = No(val)
    else:
        self._inserir(val, self.raiz)

def _inserir(self, val, node):
    if val < node.dado:
        if(node.esq != None):
            self._inserir(val, node.esq)
            node.esq.pai = node
        else:
            node.esq = No(val)
    else:
        if node.dir != None:
            self._inserir(val, node.dir)
            node.dir.pai = node
        else:
            node.dir = No(val)

def resp(self):
    if(self.raiz != None):
        return self._resp(self.raiz)
def _resp(self,node):
    aux_esq = 0
    aux_dir = 0
    if node.esq != None:
        aux_esq = self._resp(node.esq)
    if node.dir != None:
        aux_dir = self._resp(node.dir)
    if (node.esq != None) or (node.dir != None):
        return 1 + aux_esq + aux_dir
    else:
        return 0
 T = Arvore()
 T.inserir(15)
 T.inserir(9)
 T.inserir(5)
 T.inserir(12)
 T.inserir(20)
 T.resp()

After the program runs it returns me 2, why?

Answer 1

First, let’s tidy up the identation and visualize the tree formed (adding methods __str__):

class No:
    def __init__(self, dado):
        self.esq = None
        self.dir = None
        self.dado = dado

    def __str__(self):
        s = '(' + str(self.dado) + ','
        if self.esq != None:
            s += str(self.esq) + ','
        else:
            s += 'X,'
        if self.dir != None:
            s += str(self.dir) + ')'
        else:
            s += 'X)'
        return s

class Arvore:
    def __init__(self):
        self.raiz = None
    def pegarRaiz(self):
        return self.raiz

    def inserir(self, val):
        if self.raiz == None:
            self.raiz = No(val)
        else:
            self._inserir(val, self.raiz)

    def _inserir(self, val, node):
        if val < node.dado:
            if node.esq != None:
                self._inserir(val, node.esq)
                node.esq.pai = node
            else:
                node.esq = No(val)
        else:
            if node.dir != None:
                self._inserir(val, node.dir)
                node.dir.pai = node
            else:
                node.dir = No(val)

    def resp(self):
        if self.raiz != None:
            return self._resp(self.raiz)

    def _resp(self, node):
        aux_esq = 0
        aux_dir = 0
        if node.esq != None:
            aux_esq = self._resp(node.esq)
        if node.dir != None:
            aux_dir = self._resp(node.dir)
        if (node.esq != None) or (node.dir != None):
            return 1 + aux_esq + aux_dir
        else:
            return 0

    def __str__(self):
        if self.raiz != None:
            return str(self.raiz)
        else:
            return 'X'

T = Arvore()
T.inserir(15)
T.inserir(9)
T.inserir(5)
T.inserir(12)
T.inserir(20)
print(T.resp())
print(T)

Here’s the way out:

2
(15,(9,(5,X,X),(12,X,X)),(20,X,X))

See here working on ideone.

Looking at the tree we have it:

    15
   /  \
  9    20
 / \
5   12

Looking up then at the resp, he does that:

• On sheets (5, 12 and 20), aux_esq and aux_dir are zero, none of the ifYou go in and you get to the return 0

• At intermediate node (9), the three ifs enter. However, the first two do not change the values of aux_esq and aux_dir shall continue to be zero. The third shall evaluate the 1 + aux_esq + aux_dir as 1 + 0 + 0 and return 1.

• In root node (15), the three ifs enter. In the first, we will have 1 assigned to aux_esq. In the second we will have 0 assigned to aux_dir. In the third paragraph 1 + aux_esq + aux_dir will be evaluated as 1 + 1 + 0 and will return 2.

My conclusion is that this method is counting the number of internal nodes (non-leaves) of the tree. In the case of the given tree, the internal nodes are 9 and 15. This makes sense, because the if (node.esq != None) or (node.dir != None): will only enter non-leaf nodes (internal), which means that for us leaves, 0 will always be returned. As for internal nodes, we have the return 1 + aux_esq + aux_dir, which will return the number of internal nodes of each daughter subtree plus one to consider itself.