recursion_test.py

'''
Created on 06.12.2017

@author: mschroeder
'''

def create_tree(depth, n_children):
    if depth > 0:
        return [create_tree(depth - 1, n_children) for _ in range(n_children)]
    
    return [list() for _ in range(n_children)]
    
def leaf_dfs_recursive(tree):
    if len(tree) == 0:
        return [tree,]
    else:
        return sum([leaf_dfs_recursive(child) for child in tree], [])
    

def leaf_dfs_stack(tree):
    stack = []
    leaves = []
    
    for node in tree:
        stack.append(node)
        
    while True:
        try:
            node = stack.pop()
        except IndexError:
            break
        
        for child in node:
            if len(child) == 0:
                leaves.append(child)
            else:
                stack.append(child)
                
    return leaves

def compare(A, B):
    A = set(id(o) for o in A)
    B = set(id(o) for o in B)
    return len(A.symmetric_difference(B)) == 0

tree = create_tree(12, 3)
assert compare(leaf_dfs_stack(tree), leaf_dfs_recursive(tree))

#===============================================================================
# %timeit leaf_dfs_recursive(tree)
# 3.28 s ± 14.1 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
# %timeit leaf_dfs_stack(tree)
# 685 ms ± 6.46 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
#===============================================================================