Trees and hierarchical data in Intro to Computing - Interactive Code Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to create a root node named 'root' in a simple tree structure.

Intro to Computing

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

root = Node([1])

Drag options to blanks, or click blank then click option'

A"root"

Broot

CNode

Dchildren

Attempts:

3 left

💡 Hint

Common Mistakes

Forgetting quotes around the string value.

Using variable names instead of string literals.

The root node's value should be a string "root" to represent its name. Using quotes makes it a string literal.

2fill in blank

medium

Complete the code to add a child node named 'child1' to the root node's children list.

Intro to Computing

child1 = Node("child1")
root.children.[1](child1)

Drag options to blanks, or click blank then click option'

Aappend

Bextend

Cinsert

Dadd

Attempts:

3 left

💡 Hint

Common Mistakes

Using add which is not a list method.

Using extend which expects an iterable, not a single item.

To add a single child node to the list, use the append method.

3fill in blank

hard

Fix the error in the code to correctly print all child node values of the root.

Intro to Computing

for child in root.children:
    print(child.[1])

Drag options to blanks, or click blank then click option'

Aname

Bchildren

Cvalue

Dchild

Attempts:

3 left

💡 Hint

Common Mistakes

Trying to print child.children which is a list, not the name.

Using child.name which is not defined.

Each child node stores its name in the value attribute, so printing child.value shows the child's name.

4fill in blank

hard

Fill both blanks to create a dictionary mapping each child's name to the number of its children.

Intro to Computing

child_counts = {child.[1]: len(child.[2]) for child in root.children}

Drag options to blanks, or click blank then click option'

Avalue

Bchildren

Cname

Dcount

Attempts:

3 left

💡 Hint

Common Mistakes

Using name instead of value for the child's name.

Using count which is not an attribute.

Use child.value to get the child's name and child.children to get its list of children. len() counts how many children it has.

5fill in blank

hard

Fill all three blanks to create a dictionary of grandchildren counts for each child node with more than zero grandchildren.

Intro to Computing

grandchild_counts = {child.[1]: sum(len(grandchild.[2]) for grandchild in child.[3]) for child in root.children if sum(len(grandchild.children) for grandchild in child.children) > 0}

Drag options to blanks, or click blank then click option'

Avalue

Bchildren

Attempts:

3 left

💡 Hint

Common Mistakes

Mixing up keys and values in the dictionary comprehension.

Using incorrect attribute names like count or name.

The dictionary keys are child names (child.value). For each child, sum the lengths of their grandchildren lists (grandchild.children) to count grandchildren.

Practice

1. Which of the following best describes a root node in a tree structure?

easy

A. Any node that has siblings

B. A node with no children

C. A node that connects two branches

D. The top node with no parent

Solution

1. Step 1: Understand the root node concept

   The root node is the starting point of a tree and has no parent node above it.

2. Step 2: Differentiate root from other nodes

   Leaves have no children, siblings share the same parent, and connecting nodes are internal nodes, not necessarily root.

3. Final Answer:

   The top node with no parent -> Option D

4. Quick Check:

   Root = top node with no parent [OK]

Hint: Root node always has no parent node [OK]

Common Mistakes:

• Confusing root with leaf nodes
• Thinking root has siblings
• Assuming root connects branches only

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

easy

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

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

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

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

Solution

1. Step 1: Identify proper children initialization

   Children should be a list to hold multiple child nodes, so initializing with an empty list is correct.

2. Step 2: Check other attributes

   class Node: def __init__(self, value): self.value = value self.children = [] correctly sets value and children as a list; other options set children to None or 0, which is incorrect for multiple children.

3. Final Answer:

   class Node: def __init__(self, value): self.value = value self.children = [] -> Option A

4. Quick Check:

   Children list initialized as [] for multiple children [OK]

Hint: Children must be a list to hold multiple nodes [OK]

Common Mistakes:

• Setting children to None or 0 instead of a list
• Forgetting to initialize children
• Confusing parent and children attributes

3. Given the tree structure below, what is the output of a preorder traversal?

Root
├─ Child1
│  ├─ Grandchild1
│  └─ Grandchild2
└─ Child2

medium

A. ["Root", "Child1", "Grandchild1", "Grandchild2", "Child2"]

B. ["Root", "Child2", "Child1", "Grandchild1", "Grandchild2"]

C. ["Grandchild1", "Grandchild2", "Child1", "Child2", "Root"]

D. ["Child1", "Grandchild1", "Grandchild2", "Child2", "Root"]

Solution

1. Step 1: Understand preorder traversal order

   Preorder visits the root first, then recursively visits each child from left to right.

2. Step 2: Apply preorder to given tree

   Visit Root, then Child1, then Grandchild1, Grandchild2, and finally Child2.

3. Final Answer:

   ["Root", "Child1", "Grandchild1", "Grandchild2", "Child2"] -> Option A

4. Quick Check:

   Preorder = root, left to right children [OK]

Hint: Preorder = root first, then children left to right [OK]

Common Mistakes:

• Mixing preorder with postorder or inorder
• Visiting children in wrong order
• Starting traversal from a child node

4. Consider this Python code snippet for adding a child node to a tree node:

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

root = Node('root')
child = Node('child')
root.children.append(child.value)

What is the problem with this code?

medium

A. The children list is not initialized properly

B. It appends the child's value instead of the child node itself

C. The root node is missing a parent attribute

D. The child node is not created correctly

Solution

1. Step 1: Analyze the append operation

   The code appends child.value (a string) instead of the child node object itself.

2. Step 2: Understand why this is a problem

   Appending the value loses the child node's structure and children; the tree should store node objects, not just values.

3. Final Answer:

   It appends the child's value instead of the child node itself -> Option B

4. Quick Check:

   Append node objects, not just values [OK]

Hint: Append node objects, not just their values [OK]

Common Mistakes:

• Appending values instead of nodes
• Confusing node attributes with node objects
• Ignoring tree structure integrity

5. You have a company hierarchy tree where each node stores an employee's name and their direct reports as children. How would you write a function to find all employees under a given manager (including indirect reports)?

hard

A. Use a function that returns only the manager's name

B. Use a loop that only collects direct children once

C. Use a recursive function that collects children and their descendants

D. Use a function that counts the number of children without listing them

Solution

1. Step 1: Understand the problem of indirect reports

   Indirect reports are children of children, so a simple loop over direct children is not enough.

2. Step 2: Use recursion to collect all descendants

   A recursive function visits each child, then calls itself on that child to collect deeper descendants, gathering all employees under the manager.

3. Final Answer:

   Use a recursive function that collects children and their descendants -> Option C

4. Quick Check:

   Recursion collects all descendants in a tree [OK]

Hint: Recursion gathers all levels of children in a tree [OK]

Common Mistakes:

• Collecting only direct children
• Returning only the manager's name
• Counting children without listing them