python reference error in building trie tree

Question

I want to build a trivial trie tree in python, and here is my code

class Node:
    def __init__(self,ref={},num=0):
        self.ref = ref
        self.num = num

def makeTrie(node,s): 
    node.ref.setdefault(s[0],Node())
    if len(s) == 1:
        node.ref[s[0]].num += 1
        return
    makeTrie(node.ref[s[0]],s[1:])


trie = Node()
makeTrie(trie,'abcd')

print trie.ref['d'].num
print trie.ref['a'].ref['b'].ref['c'].ref['d'].num

And I am very confused,the statement print trie.ref['d'].num also have value!! But I don't know when I insert 'd' in trie ? The code above does't just insert 'd' in trie.ref['a'].ref['b'].ref['c']

What is a **trie** tree? Just asking. – Christian Tapia Jan 17 '14 at 05:16 — Christian Tapia, Jan 17 '14 at 05:16
Trie tree is like that . http://en.wikipedia.org/wiki/Trie – Ryan_Liu Jan 17 '14 at 05:18 — Ryan_Liu, Jan 17 '14 at 05:18

score 1 · Accepted Answer · edited May 23 '17 at 11:57

You've run into a problem with mutable default arguments, I think.

In the initializer for Node, you have ref={}. But {} is a dict and hence a mutable object. As such, each call to Node() calls the initializer, which mutates the same ref dictionary.

Fix (I think):

class Node:
    #                      vvvv
    def __init__(self, ref=None, num=0):
        if ref is None: # <--
            ref = {} # <--
        self.ref = ref
        self.num = num

def makeTrie(node,s):
    node.ref.setdefault(s[0],Node())
    if len(s) == 1:
        node.ref[s[0]].num += 1
        return
    makeTrie(node.ref[s[0]],s[1:])

trie = Node()
makeTrie(trie,'abcd')

try:
    print(trie.ref['d'].num)
except KeyError:
    print('KeyError occurred!')
print(trie.ref['a'].ref['b'].ref['c'].ref['d'].num)

Result:

KeyError occurred!
1

python reference error in building trie tree

1 Answers1