Height and depth of trees in Data Structures Theory - Mini Project: Build & Apply

Height and Depth of Trees

📖 Scenario: Imagine you are organizing a family tree. Each person is connected to their parents and children, forming a tree structure. Understanding the height and depth of each person in this tree helps you know how far they are from the oldest ancestor or from the root of the tree.

🎯 Goal: You will build a simple representation of a tree using a dictionary. Then, you will calculate the depth of each node (person) from the root and find the height of the tree, which is the longest path from the root to any leaf.

📋 What You'll Learn

Create a dictionary representing a tree with exact nodes and their children

Add a variable to store the root node of the tree

Write a function to calculate the depth of each node from the root

Calculate and store the height of the tree based on the depths

💡 Why This Matters

🌍 Real World

Understanding height and depth in trees helps in organizing hierarchical data like family trees, company structures, or file systems.

💼 Career

Knowledge of tree structures and their properties is essential for roles in software development, data analysis, and database management.

1

Create the tree data structure

Create a dictionary called family_tree with these exact entries: 'Grandparent': ['Parent1', 'Parent2'], 'Parent1': ['Child1', 'Child2'], 'Parent2': ['Child3'], 'Child1': [], 'Child2': [], 'Child3': [].

Data Structures Theory

# Create the family_tree dictionary with the given structure
# Your code here

Need a hint?

Use a dictionary where keys are node names and values are lists of their children.

2

Set the root of the tree

Create a variable called root and set it to the string 'Grandparent' to represent the root node of the tree.

Data Structures Theory

family_tree = {
    'Grandparent': ['Parent1', 'Parent2'],
    'Parent1': ['Child1', 'Child2'],
    'Parent2': ['Child3'],
    'Child1': [],
    'Child2': [],
    'Child3': []
}
# Set the root node of the tree
# Your code here

Need a hint?

The root is the top-most ancestor in the tree.

3

Calculate depth of each node

Write a function called calculate_depths that takes tree, node, and depth as parameters. It should return a dictionary with nodes as keys and their depths as values. Use recursion to visit each child, increasing depth by 1. Call this function with family_tree, root, and 0 and store the result in depths.

Data Structures Theory

family_tree = {
    'Grandparent': ['Parent1', 'Parent2'],
    'Parent1': ['Child1', 'Child2'],
    'Parent2': ['Child3'],
    'Child1': [],
    'Child2': [],
    'Child3': []
}
root = 'Grandparent'
# Define calculate_depths function and call it to get depths
# Your code here

Need a hint?

Use recursion to assign depth to each node, starting from 0 at the root.

4

Calculate the height of the tree

Create a variable called height and set it to the maximum value in the depths dictionary. This represents the height of the tree.

Data Structures Theory

family_tree = {
    'Grandparent': ['Parent1', 'Parent2'],
    'Parent1': ['Child1', 'Child2'],
    'Parent2': ['Child3'],
    'Child1': [],
    'Child2': [],
    'Child3': []
}
root = 'Grandparent'

def calculate_depths(tree, node, depth):
    depths = {node: depth}
    for child in tree[node]:
        depths.update(calculate_depths(tree, child, depth + 1))
    return depths

depths = calculate_depths(family_tree, root, 0)
# Calculate the height of the tree
# Your code here

Need a hint?

The height is the largest depth value among all nodes.