Attribute error in Trie implementation

I was doing this this question on leetcode and got AC in C++ . code

But same code in python3 this gives me attribute error. Probably , error is in line
if node.c[ord(s[idx])-ord(‘a’)] == None:
node.c[ord(s[idx])-ord(‘a’)] == self.Tr()

in insertu function where new node is not being assigned .Can anyone help me rectify it !
Thanks in advance :wink:

The attached link of your .Py and C++ code shows page not found.

Can you paste your code in between a pair of 3 backticks(`) or provide a Working (I mean, globally accessible) link to your code?

Problem is from leetcode u need to login however for simplicity I’m pasting it right here :

Here is the python version of code :

class Trie:
class Tr:
def init(self):
self.c = [None for _ in range(52)]
self.eof = False

def __init__(self):
    self.T = self.Tr()

def newnode(self):
    tmp = self.Tr()
    return tmp

def insertu(self,s,idx,node) -> None:
    if idx==len(s):
        node.eof = True
    if node.c[ord(s[idx])-ord('a')] == None:
        node.c[ord(s[idx])-ord('a')] == self.Tr()


def searchu(self,s:str,idx:int,node:Tr) -> bool:
    if idx == len(s):
        return node.eof
    if (not node.c[ord(s[idx])-ord('a')]):
        return False
    return self.searchu(s,idx+1,node.c[ord(s[idx])-ord('a')])

def stu(self,s:str,idx:int,node:Tr) -> bool:
    if id==len(s):
        return True
    if not node.c[ord(s[idx])-ord('a')]:
        return False
    return self.stu(s,id+1,node.c[ord(idx)--ord('a')])

def insert(self, word: str) -> None:

def search(self, word: str) -> bool:
    return self.searchu(word,0,self.T)

def startsWith(self, prefix: str) -> bool:
    return stu(prefix,0,self.T)

Gives error :
Runtime Error Message: AttributeError: ‘NoneType’ object has no attribute ‘c’
if node.c[ord(s[idx])-ord(‘a’)] == None:
Line 19 in insertu (
Line 22 in insertu (
Line 40 in insert (
result = obj.insert(
Line 59 in helper_select_method (
ret.append(DriverSolution().helper_select_method(method, params[index], obj))
Line 111 in _driver (
Line 120 in (

Meanwhile accepted CPP code :
class Trie {
/** Initialize your data structure here. /
class tr{
bool eof;
tr() {
eof = 0;
for (int i=0;i<52;++i) c[i]=NULL;

tr* T;

Trie() {
    T = new tr();

void insertU(string& s,int idx,tr*&node){
    if (idx==s.length()){
        node->eof = 1;
    if (node->c[s[idx]-'a']==NULL){
        node->c[s[idx]-'a']= new tr();

/** Inserts a word into the trie. */
void insert(string word) {

bool searchU(string& s,int id,tr*& node){
    if (id==s.length()) return (node->eof);

    if (not node->c[s[id]-'a']) return 0;

    return searchU(s,id+1,node->c[s[id]-'a']);

/** Returns if the word is in the trie. */
bool search(string word) {
    return searchU(word,0,T);

bool stU(string& s,int id,tr*& node){
    if (id==s.length()) return 1;
    if (not node->c[s[id]-'a']) return 0;
    return stU(s,id+1,node->c[s[id]-'a']);

/** Returns if there is any word in the trie that starts with the given prefix. */
bool startsWith(string prefix) {
    if (stU(prefix,0,T)) return 1;
    else return 0;



  • Your Trie object will be instantiated and called as such:
  • Trie* obj = new Trie();
  • obj->insert(word);
  • bool param_2 = obj->search(word);
  • bool param_3 = obj->startsWith(prefix);

I resolved error myself.

Thanks for your time :wink: