In [12]:

    

# Sorted n-ary tree.

'''

    [ ]
   / | \
  [ ]
 / | \

| id | data |  parent | pos |
-----------------------------
  1     A        0       1
  2     B        0       2
  3     C        1       1
  4     D        1       1
  

'''

db_n_sorted_tree = [
        [1, 'A', 0, 1],
        [2, 'B', 0, 2],
        [3, 'C', 1, 1],
        [4, 'D', 2, 1],
        [5, 'E', 3, 1],
        [6, 'F', 1, 2],
        [7, 'G', 2, 2]
    ]

ds_n_sorted_tree = {
        0 : [1, 2],
        1 : [3, 6],
        2 : [4, 7],
        3 : [5],
        4 : [None],
        5 : [None],
        6 : [None],
        7 : [None]
    }


'''

Traverse the n-ary sorted tree

start from 0

'''

def traverse(tree, index):
    if tree[index] == [None]:
        print(index)
        
    for i in tree[index]:
        traverse(tree, i)


traverse(ds_n_sorted_tree, 0)


    

    




5






    




---------------------------------------------------------------------------
KeyError                                  Traceback (most recent call last)
<ipython-input-12-cd62e499801c> in <module>()
     58 
     59 
---> 60 traverse(ds_n_sorted_tree, 0)

<ipython-input-12-cd62e499801c> in traverse(tree, index)
     55 
     56     for i in tree[index]:
---> 57         traverse(tree, i)
     58 
     59 

<ipython-input-12-cd62e499801c> in traverse(tree, index)
     55 
     56     for i in tree[index]:
---> 57         traverse(tree, i)
     58 
     59 

<ipython-input-12-cd62e499801c> in traverse(tree, index)
     55 
     56     for i in tree[index]:
---> 57         traverse(tree, i)
     58 
     59 

<ipython-input-12-cd62e499801c> in traverse(tree, index)
     55 
     56     for i in tree[index]:
---> 57         traverse(tree, i)
     58 
     59 

<ipython-input-12-cd62e499801c> in traverse(tree, index)
     51 
     52 def traverse(tree, index):
---> 53     if tree[index] == [None]:
     54         print(index)
     55 

KeyError: None

In [26]:

    

# fibonacci sequence

'''

a1 = 0
a2 = 1
a3 = a2 + a1
a4 = a3 + a2


a_n = a_n_minus_1 + a_n_minus_2

a17 = a16 + a15
a16 = a15 + a14
 

'''

memoize = [None]*200

def f_t(n):
    result = 0
    if n < 2:
        return 1
    if memoize[n]:
        print("using cached {}".format(n))
        return memoize[n]
    else:
        print("computing {}".format(n))
        result = f_t(n-1)+f_t(n-2)
    memoize[n] = result
    return result

#print(f_t(80))