GeeBrownit GeeBrownit - 2 months ago 7
Python Question

python dynamic object query

I have a python object structured like:

tree = {
"a": {
"aa": {
"aaa": {},
"aab": {},
"aac": {}
},
"ab": {
"aba": {},
"abb": {}
}
},
"b": {
"ba": {}
},
"c": {}
}


And a set of lists of strings like:

arr_1 = ["a", "ab"]
arr_2 = ["b", "ab"]
arr_3 = ["a", "ab", "aba"]


Each list defines a path of keys in the tree and I want to determine whether the list describes a valid path through the tree or not.

Currently I can achieve a case by case answer like so:

tree[arr_1[0]][arr_1[1]] # Returns correct object
tree[arr_2[0]][arr_2[1]] # Returns error
tree[arr_3[0]][arr_3[1]][arr_3[2]] # Returns correct object


Though this does not satisfy my requirements. I'd much prefer one function which will search the tree for the keys in any given list.

The following function is almost what I want but it does not handle lists of different lengths.

def is_valid(tree, arr):
obj = tree[arr[0]][arr[1]]
if len(obj) > 0:
return(obj)
else:
return("No obj")


Currently this function outputs

is_valid(tree, arr_1) # Returns the correct result
is_valid(tree, arr_2) # Returns an error
is_valid(tree, arr_3) # Returns the same result as arr_1, which is incorrect


Can anyone help me expand this function to react dynamicically to the length of the
arr
argument?

Thanks!

Answer

I think the easiest way to do this is to utilize recursion. Every sub-tree is a tree and every sub-path is a path, so we can look at whether or not the first element in the path is valid then continue on from there.

def is_valid(tree, path):

    # base case. No path would be valid for any tree
    if len(path) == 0:
        return True

    # the path must be invalid, no matter what comes before or after
    if not path[0] in tree:
        return False

    # look at the rest
    return is_valid(tree[path[0]], path[1:])

If you want the sub-tree a path describes you could instead do this:

def is_valid(tree, path):

    if len(path) == 0:
        return tree # the only difference
    if not path[0] in tree:
        return False
    return is_valid(tree[path[0]], path[1:])
Comments