Depth of a Binary Search Tree in Python

Question

In my binary search tree I am making a depth function which will tell the user what is the depth of the tree they have insert. This function will be crucial for my unique delete function that deletes a node from the largest depth-sided node. I think I know where the problem is exactly but I'm not sure.

This is my error I keep receiving.

C:\Python33\python.exe "C:/Users/koopt_000/Desktop/College/Sophomore Semester 2/Computer Science 231/Chapter7/Test.py"
Traceback (most recent call last):
PRE-ORDER TRANSVERSE:
  File "C:/Users/koopt_000/Desktop/College/Sophomore Semester 2/Computer Science 231/Chapter7/Test.py", line 19, in <module>
4
    print("The max depth of the tree is,", a.height(tree),"nodes deep.")
2
  File "C:\Users\koopt_000\Desktop\College\Sophomore Semester 2\Computer Science 231\Chapter7\BinarySearchTree.py", line 245, in height
1
3
7 
6 
5
10
None
IN-ORDER TRANSVERSE:
1
2
3
4
5
6
7
10
None
POST-ORDER TRANSVERSE:
1
    return max(BST.height(root.left), BST.height(root.right)) + 1
3
TypeError: height() missing 1 required positional argument: 'root'
2
5
6
10
7
4
None

Process finished with exit code 1

Now I Think my problem arises in this section of code:

return max(BST.height(root.left), BST.height(root.right)) + 1

I believe this statement is what is causing it due to the fact that it is making me call the BST function which the height function is already in for it to 'work'. I simply tried "height.(root.left)", which did not work because it said there is no global variable height. Which isn't the case I don't believe.

Here is my full list of code for my function, starting with my tree node, then my BST file (main), and then my test code.

class TreeNode(object):

    def __init__(self, data = None, left=None, right=None):
        self.item = data
        self.left = left
        self.right = right

    def __str__(self):
        return str(self.item)

from TreeNode import TreeNode


class BST(object):

    #------------------------------------------------------------

    def __init__(self):

        """create empty binary search tree
        post: empty tree created"""

        self.root = None
        self.size = 0

    def delete(self, item):

        """remove item from binary search tree
        post: item is removed from the tree"""

        self.root = self._subtreeDelete(self.root, item)

    #------------------------------------------------------------

    def _subtreeDelete(self, root, item):

        if root is None:   # Empty tree, nothing to do
            return None
        if item < root.item:                             # modify left
            root.left = self._subtreeDelete(root.left, item)
        elif item > root.item:                           # modify right
            root.right = self._subtreeDelete(root.right, item)
        else:                                            # delete root
            if root.left is None:                        # promote right subtree
                root =  root.right
            elif root.right is None:                     # promote left subtree
                root = root.left
            else:
                # root node can't be deleted, overwrite it with max of 
                #    left subtree and delete max node from the subtree
                root.item, root.left = self._subtreeDelMax(root.left)
        return root

 def _subtreeDelMax(self, root):

        if root.right is None:           # root is the max 
            return root.item, root.left  # return max and promote left subtree
        else:
            # max is in right subtree, recursively find and delete it
            maxVal, root.right = self._subtreeDelMax(root.right)
            return maxVal, root  

   def height(self, root):
        if root is None:
            return 0
        else:
            return max(BST.height(root.left), BST.height(root.right)) + 1

from BinarySearchTree import BST
from TreeNode import TreeNode

tree = TreeNode(4, TreeNode(2, TreeNode(1), TreeNode(3)), TreeNode (7, TreeNode(6),TreeNode(9)))


a = BST()
a._subtreeInsert(tree, 10)
a._subtreeInsert(tree, 5)
a._subtreeDelete(tree, 9)

print("PRE-ORDER TRANSVERSE:")
print(a.preOrder(tree))
print("IN-ORDER TRANSVERSE:")
print(a.inOrder(tree))
print("POST-ORDER TRANSVERSE:")
print(a.postOrder(tree))

print("The max depth of the tree is,", a.height(tree),"nodes deep.")
print("There are,", a.treeSize(tree),"nodes in this tree.")

Does anyone see the reason why my height function isn't working properly? Thanks!

SmCaterpillar · Accepted Answer · 2015-03-31 22:20:05Z

Your function height is an instance method of the class BST, you need to call it via self and not with the class BST. So in your particular case this is:

def height(self, root):
    if root is None:
        return 0
    else:
        return max(self.height(root.left), self.height(root.right)) + 1

However, your function height actually does not rely on any data associated directly with the search tree. self is only needed to continue the recursion. Thus, you could also turn it into static method via the staticmethod decorator:

@staticmethod
def height(root):
    if root is None:
        return 0
    else:
        return max(BST.height(root.left), BST.height(root.right)) + 1

Alternatively, you could also move the function out of the BST class entirely and get rid off BST.height and just call it via height.

From the code you posted, this holds for basically all functions of the BST class. I don't really see a need for it. You may only use the TreeNode and some top-level functions (without the BST class) in your python module to modify and interact with your tree.

Collectives™ on Stack Overflow

Depth of a Binary Search Tree in Python

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related