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?

Joran Beasley · Accepted Answer

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

tree = List of Nodes
nodeType1 = a dictionary consisting of nodeName=>children
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)

Searching a tree structure with a nested value?

Answers (2)

Related Questions