Count Nested Levels

In Doc2Doc, we might have documents nested inside other documents, forming a kind of tree.

Assignment

Complete the count_nested_levels function.

• Loop over document_ids in the nested_documents dictionary

• If the current document_id matches the target_document_id, return its level of nesting

• If the target_document_id is not found, recursively call count_nested_levels on the current document_id and increment the level

  • If it found the target_document_id's level, return it

• If the target_document_id doesn't exist, the function should return -1

Example

In this dictionary, the document with id 3 is nested 2 levels deep. Document 2 is nested 1 level deep.

{
    1: {
        3: {}
    },
    2: {}
}

Solution

def count_nested_levels(nested_documents, target_document_id, level=1):
    for id in nested_documents:
        #Check if current ID Matches
        if id == target_document_id:
            return level

        # Check nested documents
        foundLevel = count_nested_levels(nested_documents[id],target_document_id,level +1)
        
        # If found in nested docs, return that level
        if foundLevel != -1:
            return foundLevel
    # If we dont find anything, return -1
    return -1
        

How it Works

1️⃣ Loop Through Each Document

for id in nested_documents:

• Go through each document ID in the dictionary.

2️⃣ Check if the Current Document is the One We're Looking For

if id == target_document_id:
    return level

• If the current document ID matches the target, return the current level (how deep it is).

3️⃣ Search Inside Nested Documents

foundLevel = count_nested_levels(nested_documents[id], target_document_id, level + 1)

• If the document isn’t the target, check inside its nested documents (recursively).

• Increase the level because we’re going deeper.

4️⃣ Return the Found Level (if Exists)

if foundLevel != -1:
    return foundLevel

• If we found the target document inside a nested document, return its level.

5️⃣ If Not Found, Return -1

return -1

• If the document doesn’t exist anywhere, return -1.

Example Breakdown

Document Structure:

{
    1: {  # Level 1
        3: {}  # Level 2
    },
    2: {}  # Level 1
}

• Document 1 contains Document 3 (which is nested inside it).

• Document 2 is not nested inside anything.

Find the Depth of Document 3

count_nested_levels(nested_documents, 3)

✅ Steps:

1. Look at Document 1 (Not 3, so check inside it).

2. Look at Document 3 (Found! ✅ Return level 2).

📌 Output: 2

Visual Representation of the Document Tree

Consider this nested dictionary:

{
    1: {      # Level 1
        3: {} # Level 2
    },
    2: {}     # Level 1
}

You can picture it as a tree:

           Root
          /    \
         1      2
         |
         3

• Document 1 and Document 2 are at Level 1.

• Document 3 is nested inside Document 1, so it’s at Level 2.

---

How count_nested_levels Finds the Level

Let’s walk through finding the level of Document 3:

1. Start at the Root Level (Level 1):

   • The function is called with the whole dictionary and level=1.

   • It loops over the keys:

     • First Key: 1

       • Check: Is 1 the target?

         • No (target is 3).

       • Then, it makes a recursive call:

         count_nested_levels(nested_documents[1], target_document_id, level + 1)

         Here, nested_documents[1] is {3: {}} and level + 1 is 2.

2. Recursive Call for Document 1’s Contents (Level 2):

   • Now the function is processing the dictionary {3: {}} at Level 2.

   • It loops over the keys:

     • Key: 3

       • Check: Is 3 the target?

         • Yes!

       • The function returns 2 because it found the target at Level 2.

3. Return the Result:

   • The recursive call returns 2 to the original call.

   • Since the target was found, the original call then returns 2 as well.

Thus, Document 3 is 2 levels deep.

---

What if the Target is Not Found?

• If neither the keys at the current level nor in any nested dictionaries match the target, the function returns -1.

• This indicates that the target document doesn’t exist in the provided structure.