Trees and hierarchical data in Intro to Computing - Draw & Build Visually

Draw This - beginner

Draw a tree diagram representing a family hierarchy with 3 generations: Grandparents, Parents, and Children. Include at least 2 grandparents, 2 parents, and 3 children. Show the connections clearly to represent parent-child relationships.

10 minutes

Hint 1

Hint 2

Hint 3

Hint 4

Grading Criteria

Tree has a clear root level with grandparents

Parents are connected correctly to grandparents

Children are connected correctly to parents

All three generations are represented

Connections are clear and show parent-child relationships

Use of simple shapes or labels for each family member

Solution

Grandpa

↓

Dad

↓

Child1

This tree diagram starts with two grandparents at the top level, representing the root of the hierarchy.

Lines connect each grandparent to their children, the parents, showing the parent-child relationship.

Then, the parents are connected to their children, the third generation, showing the full family hierarchy.

This structure visually represents how data or entities can be organized in a tree with branches and levels.

Variations - 2 Challenges

[intermediate] Draw a tree diagram representing an organizational chart with 4 levels: CEO, Managers, Team Leads, and Employees. Include at least 1 CEO, 2 managers, 3 team leads, and 4 employees.

[advanced] Draw a tree diagram representing a file system hierarchy with 3 levels: Root folder, subfolders, and files. Include 1 root folder, 3 subfolders, and 5 files distributed among the subfolders.

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