lowest_common_paths.py

import os


def lowest_common_paths(path_tree, cur_path='/', depth=0, branch_limit=None, depth_limit=None):
    """
   Args:
       path_tree (dict): nested dictioary representing path structure
       branch_tolerance (int): tolerance how many branches before we call this a main folder
       depth_limit (int):
   Returns (str): list of paths that are lowest common denominators
   Usage:
       a = lowest_common_paths(make_path_tree(paths))
   """
    files = path_tree.pop('_files', None)

    if (not path_tree or
            (depth_limit and depth > depth_limit) or
            (branch_limit and len(path_tree) > branch_limit) or
            (len(path_tree) == 1)
        ):
        return [cur_path]

    paths = []

    for path, branch in path_tree.iteritems():
        paths.extend(lowest_common_paths(
            branch,
            cur_path=os.path.join(cur_path, path),
            depth=depth + 1,
            branch_limit=branch_limit,
            depth_limit=depth_limit
        ))
    return paths


if __name__ == "__main__":
    tree = {
        'a': {
            'b': {
                '_files': ['b1.jpeg', 'b2.jpeg']
            },
            '_files': ['a1.jpeg', 'a2.jpeg']
        },
        'c': {
            'd': {
                'e': {
                    'f': {
                        '_files': ['f1.jpeg', 'f2.jpeg']
                    },
                    '_files': ['e1.jpeg', 'e2.jpeg']
                }
            },
            'g': {
                'h': {
                    '_files': ['h1.jpeg', 'h2.jpeg']
                },
                'i': {
                    '_files': ['i1.jpeg', 'i2.jpeg']
                },
                '_files': ['g1.jpeg', 'g2.jpeg']
            },
            '_files': ['c1.jpeg', 'c2.jpeg']
        },
        'j': {
            'k': {
                '_files': ['k1.jpeg', 'k2.jpeg']
            },
            'l': {
                '_files': ['l1.jpeg', 'l2.jpeg']
            },
            'm': {
                '_files': ['m1.jpeg', 'm2.jpeg']
            },
            'n': {
                '_files': ['n1.jpeg', 'n2.jpeg']
            },
            'o': {
                '_files': ['o1.jpeg', 'o2.jpeg']
            },
            '_files': ['j1.jpeg', 'j2.jpeg']
        },
        '_files': ['root1.jpeg', 'root2.jpeg']
    }
    print lowest_common_paths(tree, branch_limit=3)