Traverse a data structure in python that involves nesting lists and nesting dictionaries

Question

I am trying to traverse this kind of tree, the idea is to get all "titles". Notice that this structure can get bigger, it means that every title can get more subcategories in the future. any idea?

I am tryin to do this:

def continue_searching(item):
    for i in len(item):
        if categories[i]["subcategories"]:
            continue_searching(i["subcategories"])
            print(i["subcategories"])


def give_titles(categories):
    for i in len(categories):
        if categories[i]["subcategories"]:
            continue_searching(i["subcategories"])
        print(i['title'])


categories = [
    {
        "title": "Food",
        "subcategories": [
            {"title": "Bread"},
            {
                "title": "Meat",
                "subcategories": [
                    {"title": "Pork",
                     "subcategories": [
                         {"title": "White Pork"},
                         {"title": "Red Pork"}
                     ]
                     },
                    {"title": "Beef"},
                ],
            },
            {"title": "Cheese"},
        ],
    },
    {"title": "Drinks"},
]

give_titles(categories)

Expected output:

Food
-Bread
-Meat
--Pork
---White Pork
---Red Pork
--Beef
-Cheese
Drinks

Notice that i am not using recursion because it is not clear for me when stop the calls and i do not want to saturate the call stacks.

Answer 1

Define this function:

def write_titles(cats, depth=0):
  for c in cats:
    print('-'*depth, c['title'])
    write_titles(c.get('subcategories', []), depth+1)

Then call it using write_titles(categories).

Answer 2

Traversing and printing a data structure like this is usually done using recursion as you've attempted.

In case of your code, we want to call a function repeatedly on every further nesting of the data structure.

Example code:

def print_titles(categories, depth=0):
    for category in categories:
        print('-' * depth, category['title'])
        if 'subcategories' in category:
            print_titles(category['subcategories'], depth + 1)

---

Since you've changed the question and wish a recursive-less solution, the best one is probably using iterators like so:

def print_titles(categories):
    stack = [iter(categories)]
    while stack:
        iterator = stack.pop()
        for item in iterator:
            print("-" * len(stack), item['title'])
            if 'subcategories' in item:
                stack.append(iterator)
                stack.append(iter(item['subcategories']))
                break

Answer 3

You could use recursive programming

def get_all_titles(data, output=[]):
    if isinstance(data, dict):
            output.append(data.get("title"))
            data = data.get("subcategories", [])
    if isinstance(data, list):
            for item in data:
                    get_all_titles(item)
    return output

Output

print(get_all_titles(categories))
['Food', 'Bread', 'Meat', 'Pork', 'White Pork', 'Red Pork', 'Beef', 'Cheese', 'Drinks']

Answer 4

The structure you've defined is essentially a list of separate trees.

I just iterated over each "tree" in the list and did a preorder traversal of the tree.

categories = [
{
    "title":         "Food",
    "subcategories": [
        {"title": "Bread"},
        {
            "title": "Meat",
            "subcategories": [
            {"title": "Pork",
                "subcategories": [
                {"title": "White Pork"},
                {"title": "Red Pork"}
                ]
            },
            {"title": "Beef"},
            ],
        },
        {"title": "Cheese"},
        ],
},
{"title": "Drinks"},
]


# What's really defined here is like a list of trees

def preorder(root, depth):
    print("-" * depth + root["title"])
    if "subcategories" in root:
        for child in root["subcategories"]:
            preorder(child, depth + 1)


def printCategories(categories):
    for tree in categories:
        preorder(tree, 0)
    
printCategories(categories)

This outputs:

Food
-Bread
-Meat
--Pork
---White Pork
---Red Pork
--Beef
-Cheese
Drinks

Since you also mentioned that you do not want to use recursion, just perform the traversal using your own stack as shown here.