Python – Counting number of nodes in a Binary Search Tree

pythonpython-2.7

I am trying to print the size of my binary search tree. However, what my code is doing now is printing what level each node is at. I feel as though I am putting my count += 1 in the wrong place or perhaps it might be something else. I was wondering if someone could be an extra set of eyes for me and give me a hint on how I can fix this.

output:

3
3
2
3
3
2
1

expected output:

7

my code:

def BST_size(root, count = 0):
    if root is None:
        print "size -1 (Null value in root)"
    if root is not None:
        count += 1
        if root.left is not None:
            BST_size(root.left, count)
        if root.right is not None:
            BST_size(root.right, count)
    print count

Extra parts:

class Node:
    def __init__(self,value):
        self.right = None
        self.left = None
        self.value = value


def BST_Insert(root, node):     # root --> root of tree or subtree!
    if root.value is None:
        root = node             # beginning of tree
    else:
        if root.value > node.value:     # go to left
            if root.left is None:
                root.left = node
            else:
                BST_Insert(root.left, node)

        if root.value < node.value:    # go to right
            if root.right is None:
                root.right = node
            else:
                BST_Insert(root.right, node)

r = Node(4)
# left
a = Node(2)
b = Node(1)
c = Node(3)
# right
d = Node(8)
e = Node(6)
f = Node(10)

BST_Insert(r, a)
BST_Insert(r, b)
BST_Insert(r, c)
BST_Insert(r, d)
BST_Insert(r, e)
BST_Insert(r, f)

Best Answer

There are two ways to do this.

The easy way is to return the count from each recursive call, instead of just printing it, and increment:

def BST_size(root):
    if root is None:
        return -1
    if root is not None:
        if root.left is not None:
            return 1 + BST_size(root.left)
        if root.right is not None:
            return 1 + BST_size(root.right)

def print_BST_size(root):
    size = BST_size(root)
    if size == -1:
        print "size -1 (Null value in root)"
    else:
        print "size", size

However, that still doesn't work, because you're only traversing the left side or the right side, not both. What you want is:

    count = -1
    if root is not None:
        if root.left is not None:
            count += BST_size(root.left)
        if root.right is not None:
            count += BST_size(root.right)
    return count

However, it looks like you're trying to use an accumulator, in tail-recursive style. There's really no point in doing this in Python, because Python doesn't optimize tail calls, but it's a useful skill to learn for other languages and for theoretical reasons, so…

The problem here is that you need the same value to be shared by all of the recursive calls, which means you need a mutable value. So, you can start with [0] instead of 0, and do count[0] += 1 instead of count += 1.

Or you can rearrange your code so that it doesn't use count mutably, and instead passes the updated count from one side down to the other.

Either way, you've got another problem with your code. Your recursive base case is that root is None. But you've also made it a special case, printing -1 instead of 0. You can't have it both ways.

Related Topic