Trees and hierarchical data in Intro to Computing - Practice Problems & Coding Challenges

Challenge - 5 Problems

❓ trace

intermediate

Trace the output of a simple tree traversal

Consider a tree where each node has a value and up to two children (left and right). The traversal visits nodes in this order: root, left child, right child.

What is the output sequence of node values for the tree below?

    10
   /  \
  5    15
 /    /  \
3    12  20

Intro to Computing

def preorder(node):
    if node is None:
        return []
    return [node.value] + preorder(node.left) + preorder(node.right)

# Tree structure:
# Node(10, left=Node(5, left=Node(3)), right=Node(15, left=Node(12), right=Node(20)))

# Call preorder(root)

A [5, 3, 10, 15, 12, 20]

B [3, 5, 10, 12, 15, 20]

C [10, 15, 20, 12, 5, 3]

D [10, 5, 3, 15, 12, 20]

💡 Hint

Preorder traversal visits the root node first, then recursively visits the left subtree, then the right subtree.

The preorder traversal visits nodes in the order: root, left subtree, right subtree. Starting at 10, then 5, then 3, then back up to 15, then 12, then 20.

🧠 Conceptual

intermediate

Identify the correct tree property

Which of the following statements correctly describes a binary search tree (BST)?

A For every node, all values in its left subtree are less than the node's value, and all values in its right subtree are greater.

B Every node has exactly two children, and the tree is perfectly balanced.

C Nodes are arranged so that the sum of values in the left subtree equals the sum in the right subtree.

D The tree is stored as a linked list with nodes connected only to their next sibling.

💡 Hint

Think about the ordering rule that defines a binary search tree.

A binary search tree requires that for each node, all values in the left subtree are less than the node's value, and all values in its right subtree are greater. This property allows efficient searching.

❓ Comparison

advanced

Compare tree traversal outputs

Given the same binary tree, which traversal method produces the nodes in ascending order if the tree is a binary search tree?

A Preorder traversal (root, left, right)

B Postorder traversal (left, right, root)

C Inorder traversal (left, root, right)

D Level-order traversal (breadth-first)

💡 Hint

Consider which traversal visits nodes in sorted order for a BST.

Inorder traversal visits the left subtree, then the root, then the right subtree. For a BST, this results in nodes being visited in ascending order.

❓ identification

advanced

Identify the error in tree node insertion

Consider the following pseudocode for inserting a value into a binary search tree:

function insert(node, value):
  if node is None:
    return new Node(value)
  if value < node.value:
    insert(node.left, value)
  else:
    insert(node.right, value)
  return node

What is the main problem with this code?

A It does not update the left or right child pointers after recursive insertion.

B It returns None instead of the updated node.

C It creates a new node even when the current node is not None.

D It incorrectly compares values using less than instead of greater than.

💡 Hint

Think about how recursive calls affect the tree structure and what must be done to keep the tree updated.

The recursive calls insert the new node but do not assign the returned node to the parent's left or right pointer, so the tree structure does not update correctly.

🚀 Application

expert

Calculate the height of a tree

Given the following tree structure, what is the height of the tree?

        A
       / \
      B   C
     /   / \
    D   E   F
       /     \
      G       H
               \
                I

Height is defined as the number of edges on the longest path from the root to a leaf.

A 5

B 4

C 3

D 6

💡 Hint

Trace the longest path from root A to the deepest leaf node.

The longest path is A -> C -> F -> H -> I, which has 4 edges, so the height is 4.

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