1

For example:

d = dict()

#Map "Parent" to a list of "children" values
d["Parent"] = []
d["Parent"].append("Child1")
d["Parent"].append("Child2")
d["Parent"].append("Child3")

#I know the following is wrong, but I want each list that "Parent" maps to, also to map to a list- how would I do this?
d["Parent"]["Child3"] = []
d["Parent"]["Child3"].append("GrandChild1")

This would basically look something like a tree (not binary) where there is a top level parent, pointing to its children (could be more than 2), and each can point to its multiple children. Are there other ways to do this?

Victor M
  • 27
  • 8
  • Yes, you just need a dictionary instead of a list stored against each key. But how far are you planning to go? Soon enough I think it will become unwieldy – roganjosh Dec 12 '18 at 21:41
  • `d["Child3"].append("GrandChild1")` If you just want to establish the mapping – mad_ Dec 12 '18 at 21:42
  • let's say it's at most 5 levels of depth – Victor M Dec 12 '18 at 21:44
  • But d["Child3"].append("GrandChild1") doesn't establish the mapping since it doesn't show the hierarchy of "Parent" to "Child3" to "GrandChild1" (which would look like d["Parent"]["Child3"].append("GrandChild1"), but that's not correct. – Victor M Dec 12 '18 at 21:46
  • It's basically a tree implementation with a node pointing to its children but I'm not sure how to implement it with dictionaries and lists. – Victor M Dec 12 '18 at 21:47
  • Possible duplicate of [Given a flat list of (parent,child), create a hierarchical dictionary tree](https://stackoverflow.com/questions/45460653/given-a-flat-list-of-parent-child-create-a-hierarchical-dictionary-tree) – mad_ Dec 12 '18 at 21:51
  • Using nested `defaultdict`s might be good here. https://stackoverflow.com/questions/2600790/multiple-levels-of-collection-defaultdict-in-python Could potentially be useful for you except you would have `defaultdict(list)` instead of `int`. – hqkhan Dec 12 '18 at 21:54

2 Answers2

1

I think, you're trying to do something like this:

d = {}

d["Parent"] = {}

d["Parent"]["Child1"] = {}
d["Parent"]["Child2"] = {}
d["Parent"]["Child3"] = {}

d["Parent"]["Child3"]["GrandChild1"] = {}
d["Parent"]["Child3"]["GrandChild2"] = {}

However, where are you going with this? This might not the best way to do this with Python. :-) If you can get your current code to work, you can post it to https://codereview.stackexchange.com/ afterwards. You will get valuable feedback on how to improve your code.

By the way, you can then look at the "branches" of the "tree" with dict.keys:

print(d.keys())
print(d["Parent"].keys())
print(d["Parent"]["Child3"].keys())

Which prints

dict_keys(['Parent'])
dict_keys(['Child3', 'Child2', 'Child1'])
dict_keys(['GrandChild2', 'GrandChild1'])
finefoot
  • 9,914
  • 7
  • 59
  • 102
  • I'm trying to build a tree structure with this, on which I can do a depth-first traversal. Given a JSON list: locations = [ {"id": 1, "name": "San Francisco Bay Area", "parent_id": None}, {"id": 2, "name": "San Jose", "parent_id": 3}, {"id": 3, "name": "South Bay", "parent_id": 1}, {"id": 4, "name": "San Francisco", "parent_id": 1}, {"id": 5, "name": "Manhattan", "parent_id": 6}, {"id": 6, "name": "New York", "parent_id": None} ] I want to be able to print each parent with its children: New York -Manhattan San Francisco Bay Area -San Francisco -South Bay —San Jose – Victor M Dec 12 '18 at 21:54
  • Is there a cleaner way to do this in Python than with dicts mapping to lists? – Victor M Dec 12 '18 at 21:57
  • Not sure how your code solves it. If given a JSON list where each element tells you what its parent id is (for top level parent would be None), I want to be able to create a tree structure from it where each top level parent maps to its children and each of their children (at most depth of 5). With your solution, it's unclear how I would traverse the JSON list and create each mapping. For example, if I'm iterating through the JSON list and see that "GrandChild1" is a child of "Child3" given its parent_id, how would I then know that "Child3" is a child of "Parent" and assign it the way you did? – Victor M Dec 12 '18 at 22:06
  • Yes, it could be up to 5 levels. But basically the goal is to take that JSON list and output each parent with its children underneath it and add a "-" (hyphen) at each sublevel. – Victor M Dec 12 '18 at 22:22
  • Thanks @Jayjayyy, that's really helpful. And how would you keep track of each level? For instance I want to sort each level alphabetically and add a hyphen to each level (level 1 would have '-' before the child, level 2 would have '--' before each child, etc – Victor M Dec 12 '18 at 22:27
  • I guess that would be a depth first traversal after creating the tree and keeping track of each level / using a stack. – Victor M Dec 12 '18 at 22:36
  • does this method allow you to sort each level alphabetically? – Victor M Dec 12 '18 at 22:47
0

Being interested in how to do trees in python, I searched around and came across some example code on GitHub for a One-line Tree in Python.

Create a tree from a defaultdict:

from collections import defaultdict
def tree(): return defaultdict(tree)

Build your tree structure:

t = tree()
t['San Francisco Bay Area']['San Francisco']
t['San Francisco Bay Area']['South Bay']['San Jose']
t['New York']['Manhattan']

And print it out;

import json
print(json.dumps(t))

{"New York": {"Manhattan": {}}, "San Francisco Bay Area": {"San Francisco": {}, "South Bay": {"San Jose": {}}}}

There's further information on iteration and, in the comments, more useful code and suggestions on loading it from json and pretty printing the structure.

Tony
  • 9,672
  • 3
  • 47
  • 75