Why Trees Exist and What Linked Lists and Arrays Cannot Do in DSA Python - See It Work

Why Trees Exist and What Linked Lists and Arrays Cannot Do

📖 Scenario: Imagine you are organizing a family reunion. You want to keep track of family members and their relationships, like parents and children. Using just a list or an array makes it hard to show who is related to whom. Trees help us show these connections clearly.

🎯 Goal: You will build a simple family tree using nodes connected like a tree. You will see why linked lists and arrays cannot easily represent these relationships.

📋 What You'll Learn

Create a class called FamilyMember with a name and a list of children

Create a root family member called grandparent with the name 'Grandpa Joe'

Add two children to grandparent: 'Uncle Bob' and 'Aunt Mary'

Add one child to 'Uncle Bob': 'Cousin Tim'

Print the family tree showing each member and their children

💡 Why This Matters

🌍 Real World

Trees are used to represent hierarchical data like family trees, company structures, file systems, and more.

💼 Career

Understanding trees helps in software development, database design, and solving problems involving hierarchical data.

1

Create the FamilyMember class and the grandparent node

Create a class called FamilyMember with an __init__ method that takes name and initializes self.children as an empty list. Then create a variable called grandparent as a FamilyMember with the name 'Grandpa Joe'.

DSA Python

# Your code here

Hint

Think of each family member as a node. Each node has a name and a list to hold children.

2

Add children to the grandparent

Create two FamilyMember instances named uncle_bob with 'Uncle Bob' and aunt_mary with 'Aunt Mary'. Add both to grandparent.children list.

DSA Python

class FamilyMember:
    def __init__(self, name):
        self.name = name
        self.children = []

grandparent = FamilyMember('Grandpa Joe')
# Your code here

Hint

Use the append method to add children to the children list.

3

Add a child to Uncle Bob

Create a FamilyMember named cousin_tim with 'Cousin Tim' and add it to uncle_bob.children list.

DSA Python

class FamilyMember:
    def __init__(self, name):
        self.name = name
        self.children = []

grandparent = FamilyMember('Grandpa Joe')

uncle_bob = FamilyMember('Uncle Bob')
aunt_mary = FamilyMember('Aunt Mary')

grandparent.children.append(uncle_bob)
grandparent.children.append(aunt_mary)
# Your code here

Hint

Remember to add the new child to the correct parent's children list.

4

Print the family tree

Write a function called print_family that takes a FamilyMember and an optional level (default 0). It prints the member's name with indentation based on level. Then it calls itself recursively for each child with level + 1. Finally, call print_family(grandparent) to display the tree.

DSA Python

class FamilyMember:
    def __init__(self, name):
        self.name = name
        self.children = []

grandparent = FamilyMember('Grandpa Joe')

uncle_bob = FamilyMember('Uncle Bob')
aunt_mary = FamilyMember('Aunt Mary')

grandparent.children.append(uncle_bob)
grandparent.children.append(aunt_mary)

cousin_tim = FamilyMember('Cousin Tim')
uncle_bob.children.append(cousin_tim)

# Your code here

Hint

Use recursion to print each member and their children with indentation.

Practice

1. Why do trees exist as a data structure when we already have arrays and linked lists?

easy

A. Because trees can represent hierarchical relationships which arrays and linked lists cannot

B. Because trees use less memory than arrays and linked lists

C. Because trees are easier to implement than arrays and linked lists

D. Because trees always provide faster access than arrays and linked lists

Solution

1. Step 1: Understand the limitation of arrays and linked lists

   Arrays and linked lists store data in a linear order, which makes it hard to represent hierarchical or branching relationships.

2. Step 2: Identify the unique feature of trees

   Trees allow nodes to have multiple children, representing parent-child relationships naturally, which arrays and linked lists cannot do efficiently.

3. Final Answer:

   Trees represent hierarchical relationships which arrays and linked lists cannot -> Option A

4. Quick Check:

   Hierarchy needs trees = A [OK]

Hint: Trees model hierarchy; arrays and lists are linear [OK]

Common Mistakes:

• Thinking trees always use less memory
• Believing trees are simpler to implement
• Assuming trees always have faster access

2. Which of the following is the correct way to define a simple tree node class in Python?

easy

A. class Node:
def __init__(self, value):
self.value = value
self.next = None

B. class Node:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
self.next = None

C. class Node:
def __init__(self, value):
self.value = value
self.children = []

D. class Node:
def __init__(self, value):
self.value = value
self.prev = None

Solution

1. Step 1: Identify the tree node structure

   A tree node typically stores a value and a list of children nodes to represent branches.

2. Step 2: Match the class definition

   class Node: def __init__(self, value): self.value = value self.children = [] defines a node with a value and a children list, which fits a general tree node structure.

3. Final Answer:

   Node with value and children list -> Option C

4. Quick Check:

   Tree nodes have children list = D [OK]

Hint: Tree nodes have children list, not next or prev pointers [OK]

Common Mistakes:

• Using 'next' pointer like in linked lists
• Using 'prev' pointer which is for doubly linked lists
• Adding unrelated pointers like 'next' in trees

3. What will be the output of this code that tries to print values in a simple tree node?

class Node:
    def __init__(self, value):
        self.value = value
        self.children = []

root = Node(1)
child1 = Node(2)
child2 = Node(3)
root.children.append(child1)
root.children.append(child2)

for child in root.children:
    print(child.value)

medium

A. Error: 'Node' object is not iterable

B. 1 2 3

C. 1

D. 2 3

Solution

1. Step 1: Understand the tree structure created

   Root node has value 1 and two children nodes with values 2 and 3.

2. Step 2: Trace the loop printing child values

   The loop iterates over root.children, printing each child's value: 2 then 3.

3. Final Answer:

   2 3 -> Option D

4. Quick Check:

   Children values printed = A [OK]

Hint: Loop prints children values, not root value [OK]

Common Mistakes:

• Printing root value inside loop
• Confusing children list with node itself
• Expecting root value to print in loop

4. Find the error in this code that tries to add a child to a tree node:

class Node:
    def __init__(self, value):
        self.value = value
        self.children = None

root = Node(1)
child = Node(2)
root.children.append(child)

medium

A. append() method does not exist for lists

B. children should be initialized as an empty list, not None

C. Node class should not have a children attribute

D. Cannot create child nodes before root node

Solution

1. Step 1: Check children initialization

   children is set to None, so it is not a list and cannot use append().

2. Step 2: Identify correct initialization

   children should be an empty list [] to allow appending child nodes.

3. Final Answer:

   children should be initialized as an empty list, not None -> Option B

4. Quick Check:

   children must be list for append() [OK]

Hint: Initialize children as [] to use append() [OK]

Common Mistakes:

• Setting children to None instead of list
• Trying to append to None type
• Ignoring initialization of children attribute

5. You want to represent a company's organizational chart where each employee can have multiple subordinates. Which data structure is best and why?

hard

A. Tree, because it naturally models hierarchical relationships

B. Array, because it stores data in order

C. Linked list, because it connects employees one after another

D. Stack, because it follows last-in-first-out order

Solution

1. Step 1: Understand the problem context

   An organizational chart shows who reports to whom, forming a hierarchy with multiple subordinates per employee.

2. Step 2: Match data structure to hierarchy

   Trees allow each node (employee) to have multiple children (subordinates), perfectly modeling this hierarchy.

3. Final Answer:

   Tree, because it naturally models hierarchical relationships -> Option A

4. Quick Check:

   Hierarchy needs trees = B [OK]

Hint: Hierarchy means use trees, not linear structures [OK]

Common Mistakes:

• Choosing arrays or lists for hierarchical data
• Confusing stack usage with hierarchy
• Ignoring multiple children per node