how to fix the count function

Question

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

def list_to_tree(alist):
    if alist == None:
        return None
    else:
        return TN(alist[0],list_to_tree(alist[1]),list_to_tree(alist[2])) 

def str_tree(atree,indent_char ='.',indent_delta=2):
    def str_tree_1(indent,atree):
        if atree == None:
            return ''
        else:
            answer = ''
            answer += str_tree_1(indent+indent_delta,atree.right)
            answer += indent*indent_char+str(atree.value)+'\n'
            answer += str_tree_1(indent+indent_delta,atree.left)
            return answer
    return str_tree_1(0,atree) 

def count(t,value):
    nodes = []
    num = 0
    nodes.append(t)
    while len(nodes) > 0:
        if nodes[0] == value:
            num += 1
        next = nodes.pop(0)
        count(next,value)
    return num

I need to write a recursive function count (other three functions cannot be changed); it is passed balanced binary tree and a value as arguments. It returns the number of times the values is in the tree. In the binary tree below, count(tree,1) returns 1, count(tree,2) returns 2, count(tree,3) returns 4

..1
....3
3
....3
..2
......2
....3

I called the following functions

tree = list_to_tree([3, [2, None, [3, None, None]], [1, [3, None, None], None]])
print('\nfor tree = \n',str_tree(tree))
for i in irange(1,3):
    print('count(tree,'+str(i)+') = ', count(tree,i))

but it shows the error that "RecursionError: maximum recursion depth exceeded in comparison" can someone help me to fix the count function? Thanks in advance.

Python can only recurse for so long http://stackoverflow.com/questions/3323001/what-is-the-maximum-recursion-depth-in-python-and-how-to-increase-it/41916112#41916112 ... However I don't see that that should be a problem with your program. I think however your exit condition isn't setup correctly. Does the length of nodes ever hit 0? I added print statement and the length of nodes only ever goes as low as 1. Which means that your while loop never exits. — reticentroot, Feb 27 '17 at 02:38
You have infinite recursion. You do `nodes.append(t)`, then `next = nodes.pop(0)` (now `next` equals `t`), then call `count(t, value)`. — Aran-Fey, Feb 27 '17 at 02:42
BTW, you shouldn't use `next` as a variable name because that shadows the built-in `next` function. — PM 2Ring, Feb 27 '17 at 03:21

Paul Panzer · Accepted Answer · 2017-02-27T03:22:05.517

1

If you look carefully at your code you'll see that you set up an empty nodes list, fill it with t, so the while loop is always entered you'll always pop t into next and always call the function with precisely the same parameters. That is of course an infinite recursion.

Here is one simple way of setting it up correctly:

def count(tree, number):
    if tree is None:
        return 0
    else:
        return (number == tree.value) + count(tree.left, number) \
            + count(tree.right, number)

edited Feb 27 '17 at 03:22

answered Feb 27 '17 at 02:52

Paul Panzer

51,835
3
54
99

hi, I tried your code but it still gives me the same error. – zeyuxie Feb 27 '17 at 03:06

score 0 · Answer 2 · answered Feb 27 '17 at 03:18

Another way to go about it is using transversal, in a typical tree there is a root and a node subclass. Your tree is missing that structure so it looks a bit weird. To use transversal I'm using a global var to keep track of the counter.

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

def list_to_tree(alist):
    if alist == None:
        return None
    else:
        return TN(alist[0],list_to_tree(alist[1]),list_to_tree(alist[2])) 

def str_tree(atree,indent_char ='.',indent_delta=2):
    def str_tree_1(indent,atree):
        if atree == None:
            return ''
        else:
            answer = ''
            answer += str_tree_1(indent+indent_delta,atree.right)
            answer += indent*indent_char+str(atree.value)+'\n'
            answer += str_tree_1(indent+indent_delta,atree.left)
            return answer
    return str_tree_1(0,atree) 


NUM = 0
def count(t,value):
    global NUM
    NUM = 0
    if t != None:
      if t.left == None and t.right == None:
        if t.value == value:
          return 1
        else:
          return 0
      else:
        _count(t, value)
    return NUM


def _count(t, value):
    if t.left != None:
        _count(t.left, value)

    if t.value == value:
        global NUM
        NUM += 1

    if t.right != None:
        _count(t.right, value)


tree = list_to_tree([3, [2, None, [3, None, None]], [1, [3, None, None], None]])
print(str_tree(tree))
print("count 1", count(tree, 1))
print("count 2", count(tree, 2))
print("count 3", count(tree, 3))

how to fix the count function

2 Answers2