Searching a tree structure with a nested value?

Question

Input: The tree structure is a list of financial accounts that are separated out in a hierarchical order of parent/children accounts. Any given account can have any number of parents/children. In the Python structure, each child is a list that can contain any number of dictionaries and/or text values. The dictionaries represent children that point to additional accounts whereas the text value represents a child that has no further descendants. Here is some example input formatted in JSON (to test it, please convert it back in Python):

[  
   {  
      "Assets":[  
         {  
            "Bank":[  
               "Car",
               "House"
            ]
         },
         {  
            "Savings":[  
               "Emergency",
               {  
                  "Goals":[  
                     "Roof"
                  ]
               }
            ]
         },
         "Reserved"
      ]
   }
]

Behind the scenes there is an input file that contains account definitions that look like this:

Assets:Bank:House
Assets:Savings:Emergency
Assets:Savigs:Goals:Roof

I have existing code that parses and creates the tree structure seen above.

The Goal: The end goal is to provide auto-completion utilizing a given string input by searching through the tree. Using the sample input above, the following inputs would produce their respective outputs:

"Assets" => ["Bank, "Savings", "Reserved"]
"Assets:Bank" => ["Car", "House"]
"Assets:Savings:Goals" => ["Roof"]

Partial Solution: The recursion is where I am getting tripped up. I was able to create code that can handle giving results for a "root" account, but I'm not sure how to make it recursive to provide results for child accounts. Here's the code:

def search_tree(account, tree):
    # Check to see if we're looking for a root level account
    if isinstance(account, str) and ":" not in account:
        # Collect all keys in the child dictionaries
        keys = {}
        for item in tree:
            if isinstance(item, dict):
                keys[item.keys()[0]] = item

        # Check to see if the input matches any children
        if account in keys:
            # Collect all children of this account
            children = []

            for child in keys[account][account]:
                if isinstance(child, str):
                    children.append(child)
                else:
                    children.append(child.keys()[0])

            return children

# tree = .....
account = "Assets"
print search_tree(account, tree) # Would produce ["Bank", "Savings", "Reserved"]
# In the future I would provide "Assets:Bank" as the account string and get back the following: ["Car", "House"]

How would I make this recursive to search down to n children?

Answer 1

Im not going to actually answer your question (with regards to your specific stdout output requirements) but i will help show you how to search a tree structure

first describe your tree structure

1. tree = List of Nodes
2. nodeType1 = a dictionary consisting of nodeName=>children
3. nodeType2 = a simple basestring (nodeName) with no children (leaf node)

now we can start to write a recursive solution

def search(key,tree):
    if isinstance(tree,(list,tuple)): # this is a tree
        for subItem in tree: # search each "node" for our item
            result = search(key,subItem)
            if result:
                return result
    elif isinstance(tree,dict): # this is really a node (nodeType1)
        nodeName,subTree = next(tree.iteritems())
        if nodeName == key: # match ... in your case the key has many parts .. .you just need the "first part"
            print "Found:",key
            return subTree
        else: # did not find our key so search our subtree
            return search(key,subTree)

    elif isinstance(tree,basestring): #leaf node
        if tree == key: # found our key leaf node
            print "Found",key
            return tree

this is really only a very general solution, it can be used to search for a single entry (ie "House" or "Accounts" ... it does not record a path that was used to arrive at the solution)

now lets return to examining your problem statement

a key is a multipart key Part1:part2:part3 so lets start working on this problem

def search_multipartkey(key,T,separator=":"):
    result = T
    for part in key.split(separator):
        result = search(part,result)
        if not result:
           print "Unable to find part:",part
           return False
        else:
           print "Found part %s => %s"%(part,result)
    return result

you can almost certainly improve upon this but this gives a nice starting point (although it is not recursive in the way perhaps someone was hoping for)

Answer 2

Incomplete (out of time, but I am sure you will manage to integrate your tests):

tree =  [
        {"Assets":  [
                    {"Bank":    [
                                "Car",
                                "House"
                                ]
                    },
                    {"Savings": [
                                "Emergency",
                                {"Goals":
                                        ["Roof"]
                                }
                                ]
                    },
                    "Reserved"
                    ]
      }
   ]



def search_tree(account, tree, level):
    """ """
    print("account", account)
    print("tree", tree)
    print("level", level)
    print("-------------")

    if account == []:
        return

    r = None
    for d in tree:
        print("a:",account[0])
        print("d:",d)
        try:
            newtree = d[account[0]]
            newaccount = account[1:]
            print("new:", newtree, newtree )
            r = search_tree(newaccount, newtree, level+1)
        except Exception as e:
            print("failed because:", e)
    return r

account = "Assets:Bank"
search_tree(account.split(":"), tree, 0)

Output:

> py -3 t.py
account ['Assets', 'Bank']
tree [{'Assets': [{'Bank': ['Car', 'House']}, {'Savings': ['Emergency', {'Goals': ['Roof']}]}, 'Reserved']}]
level 0
-------------
a: Assets
d: {'Assets': [{'Bank': ['Car', 'House']}, {'Savings': ['Emergency', {'Goals': ['Roof']}]}, 'Reserved']}
new: [{'Bank': ['Car', 'House']}, {'Savings': ['Emergency', {'Goals': ['Roof']}]}, 'Reserved'] [{'Bank': ['Car', 'House']}, {'Savings': ['Emergency', {'Goals': ['Roof']}]}, 'Reserved']
account ['Bank']
tree [{'Bank': ['Car', 'House']}, {'Savings': ['Emergency', {'Goals': ['Roof']}]}, 'Reserved']
level 1
-------------
a: Bank
d: {'Bank': ['Car', 'House']}
new: ['Car', 'House'] ['Car', 'House']
account []
tree ['Car', 'House']
level 2
-------------
a: Bank
d: {'Savings': ['Emergency', {'Goals': ['Roof']}]}
failed because: 'Bank'
a: Bank
d: Reserved
failed because: string indices must be integers

---

Still no tests, but returns what you want (for this single case):

def search_tree(account, tree, level):
    """ """
    #print()
    #print()
    #print("account", account)
    #print("tree", tree)
    #print("level", level)
    #print("-------------")

    if account == []:
        #print("reached end")
        #print("tree", tree)
        return tree

    r = None
    for d in tree:
        #print("a:",account[0])
        #print("d:",d)
        try:
            newtree = d[account[0]]
            newaccount = account[1:]
            #print("new:", newtree, newtree )
            r = search_tree(newaccount, newtree, level+1)
        except Exception as e:
            #print("failed because:", e)
            pass
    return r

account = "Assets:Bank"
print( search_tree(account.split(":"), tree, 0) ) # --> ['Car', 'House']