Python recursive function with helper function

user_17303450 0
Viewed 81

I am writing a function to determine the size of a binary search tree. I tried it in a recursive way:

def size(self) -> int: #self representing the whole bst
        """Return number of nodes contained in the tree."""

        if self._root is None:
            return 0
        else:
            return self._size(self, 0, self._root)

def _size(self, current_size, current_node):

        if current_node != None:
            current_size += 1
        if current_node.left != None:
                current_size += self._size(current_size, current_node.left)
        if current_node.right != None:
                current_size += self._size(current_size, current_node.right)

        return current_size

However, this throws a TypeError for the line:

return self._size(self, 0, self._root)
TypeError: 'int' object is not callable

I am new to the recursive functions and somehow cannot really find out how the helper function and the original function should work together and if my approach is going into the right direction. Therefore, any help is much appreciated.

Here are the codes for the classes:

from typing import Any


class TreeNode:

    def __init__(self, key: int, value: Any, right: 'TreeNode' = None,
                 left: 'TreeNode' = None, parent: 'TreeNode' = None):
        """Initialize TreeNode.

        Args:
            key (int): Key used for sorting the node into a BST.
            value (Any): Whatever data the node shall carry.
            right (TreeNode, optional): Node to the right, with a larger key. Defaults to None.
            left (TreeNode, optional): Node to the left, with a lesser key. Defaults to None.
            parent (TreeNode, optional): Parent node. Defaults to None.
        """
        self.key = key
        self.value = value
        self.right = right
        self.left = left
        self.parent = parent


from tree_node import TreeNode


class BinarySearchTree:
    """Binary-Search-Tree implemented for didactic reasons."""

    def __init__(self, root: TreeNode = None):
        """Initialize BinarySearchTree.

        Args:
            root (TreeNode, optional): Root of the BST. Defaults to None.
        
        """
        self._root = root
        self._size = 0 if root is None else 1
binary-search-tree recursion python
2 Answers

There are the following issues:

  • _size is an instance attribute that is set in the __init__ function. That means that self._size will refer to that attribute, and not to the class method with the same name. This is the cause of the error you get. You should use a different name for these two things: one name for the integer size, and another for the helper function that will calculate the size recursively. I suggest to use _sizerecur as name for the helper method -- and will refer to it that way in the next point:

  • self._sizerecur(self, 0, self._root) should not pass self as argument, as that parameter is already getting the value of self by this type of method-call syntax (the prefix in the dot notation serves as that argument).

  • if current_node != None should have all the rest of that code in its block, otherwise current_node.left will still be evaluated when current_node is None, leading to an error.

  • The size is not calculated correctly. There are essentially two ways to implement this recursion, and your code seems to mix both of these, making it incorrect: When you pass the current size as argument to the recursive call, and that call returns the updated value, you should not add that to the original size you already passed to it. By doing that, you have double counting. You should either just assign it back to your variable (not adding to it), or (better), not pass the current count as argument, but let each recursive call start counting from 0.

Here is a correction keeping the existing current_size parameter:

    def size(self) -> int:
        if self._root is None:
            return 0
        else:
            return self._sizerecur(0, self._root) # don't pass self as arg

    # A distinct name for this method
    def _sizerecur(self, current_size, current_node):
        if current_node:
            current_size += 1
        if current_node.left:
            # don't ADD again to current size
            current_size = self._sizerecur(current_size, current_node.left)
        if current_node.right:
            current_size = self._sizerecur(current_size, current_node.right)

        return current_size

But as said, it is better practice to implement this recursive function without current_size parameter. Instead of updating the counter while you recur deeper, update it while getting out of recursion:

    def size(self) -> int:
        if self._root is None:
            return 0
        else:
            return self._sizerecur(self._root)

    def _sizerecur(self, current_node):
        current_size = 0
        if current_node:
            current_size = 1
            if current_node.left:
                current_size += self._sizerecur(current_node.left)
            if current_node.right:
                current_size += self._sizerecur(current_node.right)
        return current_size
user_54598390

You don't need to pass self explicitly when calling self.function_name()

return self._size(0, self._root)

user_32118010
Related