CODEWITHSUNDEEP
pythonpython-2.7
Liondancer
Liondancer

Reputation: 16469

Counting number of nodes in a Binary Search Tree

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)

Upvotes: 2

Views: 20873

Answers (6)

Jija
Jija

Reputation: 1

You could use something like this:

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

and invoke it like below:

print ("\nCount of Nodes :" + str(countNodes(root)))

Upvotes: 0

abarnert
abarnert

Reputation: 365707

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.

Upvotes: 4

brunsgaard
brunsgaard

Reputation: 5158

Here is a short answer

You have to do tree treversal, where the function returns the number of nodes below + 1 (itself)

Pseudo code:

def counter(t):
  rCount = counter(t.right)
  lCount = counter(t.left)
  return 1 + rCount + lCount

Upvotes: 1

Vaibhav Desai
Vaibhav Desai

Reputation: 2728

def BST_size(root):
    if root is None:
        return 0
    else:
        return BST_size(root.left) + BST_size(root.right) + 1

print "Size is: " + str(BST_size(r))

Upvotes: 2

Maciej Gol
Maciej Gol

Reputation: 15854

def BST_size(root, count = 0):
    if root is None:
        return count

    return BST_size(root.left, BST_size(root.right, count + 1))

Upvotes: 4

Joran Beasley
Joran Beasley

Reputation: 113958

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

Upvotes: 1

Related Questions