Home/ Questions/Q 13221
Next
In Process

askthedev.com Latest Questions

Asked: 2024-09-26T21:37:44+05:30 In:

How to Determine a Person’s Level in a Family Tree Using Python?

I’ve been diving into some interesting programming challenges recently, and one that got me thinking involves calculating a pedigree. So here’s the scenario: Imagine you’ve got a family tree represented as a list of tuples, where each tuple consists of a person and their parents. The goal is to determine the level of a person in the tree, which is determined by how many generations they are from the oldest known ancestor.

For example, let’s say we have the following data structure:

“`python
family = [
(‘grandparent’, None, None),
(‘parent’, ‘grandparent’, None),
(‘child’, ‘parent’, None),
(‘grandchild’, ‘child’, None)
]
“`

In this structure, ‘grandparent’ is at the top, and ‘grandchild’ is at the bottom. What I need help with is figuring out how to write a function that takes a person’s name and returns their level in the pedigree (starting from 0 for the oldest ancestor). So for ‘grandparent’, the function would return 0, for ‘parent’, it would return 1, for ‘child’, it would return 2, and for the ‘grandchild’, it would return 3.

I started sketching out some ideas, but it quickly became more complicated than I anticipated. I want to make sure that the function can handle cases where the person doesn’t exist, and maybe it should return -1 in such cases.

I’ve thought about using a dictionary to map each person to their parents, but I’m not sure how to traverse the tree recursively and count the levels accurately.

Does anyone have a straightforward solution or even a useful approach to tackle this problem? I’m all ears for any tips or code snippets you can share to help me nail this down!

Share

    Leave an answer

    You must login to add an answer.

    Need An Account,

    2 Answers

    1. To solve the problem of determining a person’s level in a family tree represented as a list of tuples, we can define a function that constructs a dictionary mapping each person to their parent. This representation allows easy traversal of the family tree to count the levels from the individual to their oldest known ancestor. Below is a code snippet that demonstrates this approach:

      def get_level(family, person):
    # Create a dictionary mapping each person to their parents
    tree = {p[0]: p[1] for p in family}
    
    # Initialize level
    level = 0
    
    # Traverse the tree upwards to count the levels
    while person in tree:
        parent = tree[person]
        if parent is None:  # Found the oldest ancestor
            return level
        person = parent
        level += 1
    
    return -1  # Person not found in the tree

# Example usage
family = [
    ('grandparent', None),
    ('parent', 'grandparent'),
    ('child', 'parent'),
    ('grandchild', 'child')
]
print(get_level(family, 'grandchild'))  # Output: 3
print(get_level(family, 'parent'))      # Output: 1
print(get_level(family, 'unknown'))     # Output: -1


    2. def get_level(family, person):
    # Create a dictionary to map each person to their parents
    family_dict = {child: parent for child, parent, _ in family}

    # Start from the person and count levels
    level = 0
    current = person
    
    while current is not None:
        if current not in family_dict:
            return -1  # Person doesn't exist
        current = family_dict[current]
        level += 1
    
    return level - 1  # Subtract one to account for the loop incrementing after the last ancestor

# Example usage
family = [
    ('grandparent', None, None),
    ('parent', 'grandparent', None),
    ('child', 'parent', None),
    ('grandchild', 'child', None)
]

print(get_level(family, 'grandparent'))  # Output: 0
print(get_level(family, 'parent'))       # Output: 1
print(get_level(family, 'child'))        # Output: 2
print(get_level(family, 'grandchild'))   # Output: 3
print(get_level(family, 'nonexistent'))  # Output: -1

    Related Questions