current community

your communities

more stack exchange communities

company blog
Stack Exchange Inbox Reputation and Badges
tour help
Join the Stack Overflow Community
Stack Overflow is a community of 4.7 million programmers, just like you, helping each other.
Join them; it only takes a minute:
Sign up
up vote 1 down vote favorite

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!

share|improve this question
    
First your 'set of dicts' is really a 'list of str'. Second try to do for key in arr: to loop over the keys in is_valid. Third, not sure if this is hw or the use case, but if you can, you can try creating an actual tree and searching that. – postelrich 19 hours ago
up vote 3 down vote accepted

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. Any 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:])
share|improve this answer
    
Thanks! That is perfect! – GeeBrownit 19 hours ago
    
If it answered your question I would appreciate it if you accepted the answer. Glad I could help. – jcolemang 18 hours ago
    
Apologies, have done so now. – GeeBrownit 18 hours ago
    
No problem at all, thanks – jcolemang 18 hours ago

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.