GeeBrownit - 5 months ago 21

Python Question

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`

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:])
```